Selection of Switching Sites in All-Optical Nework Topology Design

In this paper, we consider the problem of topology design for optical networks. We investigate the problem of selecting switching sites to minimize total cost of the optical network. The cost of an optical network can be expressed as a sum of three main factors: the site cost, the link cost, and the switch cost. To the best of our knowledge, this problem has not been studied in its general form as investigated in this paper. We present a mixed integer quadratic programming (MIQP) formulation of the problem to find the optimal value of the total network cost. We also present an efficient heuristic to approximate the solution in polynomial time. The experimental results show good performance of the heuristic. The value of the total network cost computed by the heuristic varies within 2% to 21% of its optimal value in the experiments with 10 nodes. The total network cost computed by the heuristic for 51% of the experiments with 10 node network topologies varies within 8% of its optimal value. We also discuss the insight gained from our experiments.

Killer Whales and Marine Mammal Trends in The North Pacific—A Re-Examination of Evidence for Sequential Megafauna Collapse and the Prey-Switching Hypothesis

Springer et al. (2003) contend that sequential declines occurred in North Pacific populations of harbor and fur seals, Steller sea lions, and sea otters. They hypothesize that these were due to increased predation by killer whales, when industrial whaling’s removal of large whales as a supposed primary food source precipitated a prey switch. Using a regional approach, we reexamined whale catch data, killer whale predation observations, and the current biomass and trends of potential prey, and found little support for the prey-switching hypothesis. Large whale biomass in the Bering Sea did not decline as much as suggested by Springer et al., and much of the reduction occurred 50–100 yr ago, well before the declines of pinnipeds and sea otters began; thus, the need to switch prey starting in the 1970s is doubtful. With the sole exception that the sea otter decline followed the decline of pinnipeds, the reported declines were not in fact sequential. Given this, it is unlikely that a sequential megafaunal collapse from whales to sea otters occurred. The spatial and temporal patterns of pinniped and sea otter population trends are more complex than Springer et al. suggest, and are often inconsistent with their hypothesis. Populations remained stable or increased in many areas, despite extensive historical whaling and high killer whale abundance. Furthermore, observed killer whale predation has largely involved pinnipeds and small cetaceans; there is little evidence that large whales were ever a major prey item in high latitudes. Small cetaceans (ignored by Springer et al.) were likely abundant throughout the period. Overall, we suggest that the Springer et al. hypothesis represents a misleading and simplistic view of events and trophic relationships within this complex marine ecosystem.

Applications of Linear Programming to Coding Theory

Maximum-likelihood decoding is often the optimal decoding rule one can use, but it is very costly to implement in a general setting. Much effort has therefore been dedicated to find efficient decoding algorithms that either achieve or approximate the error-correcting performance of the maximum-likelihood decoder. This dissertation examines two approaches to this problem. In 2003 Feldman and his collaborators defined the linear programming decoder, which operates by solving a linear programming relaxation of the maximum-likelihood decoding problem. As with many modern decoding algorithms, is possible for the linear programming decoder to output vectors that do not correspond to codewords; such vectors are known as pseudocodewords. In this work, we completely classify the set of linear programming pseudocodewords for the family of cycle codes. For the case of the binary symmetric channel, another approximation of maximum-likelihood decoding was introduced by Omura in 1972. This decoder employs an iterative algorithm whose behavior closely mimics that of the simplex algorithm. We generalize Omura's decoder to operate on any binary-input memoryless channel, thus obtaining a soft-decision decoding algorithm. Further, we prove that the probability of the generalized algorithm returning the maximum-likelihood codeword approaches 1 as the number of iterations goes to infinity.