We consider several combinatorial optimization problems in a geometric set- ting. The first problem we consider is the problem of clustering to minimize the sum of radii. Given a positive integer k and a set of points with interpoint distances that satisfy the definition of being a "metric", we define a ball centered at some input point and having some radius as the set of all input points that are at a distance smaller than the radius of the ball from its center. We want to cover all input points using at most k balls so that the sum of the radii of the balls chosen is minimized. We show that when the points lie in some Euclidean space and the distance measure is the standard Euclidean metric, we can find an exact solution in polynomial time under standard assumptions about the model of computation. The second problem we consider is the Network Spanner Topology Design problem. In this problem, given a set of nodes in the network, represented by points in some geometric setting - either a plane or a 1.5-D terrain, we want to compute a height assignment function h that assigns a height to a tower at every node such that the set of pairs of nodes that can form a direct link with each other under this height function forms a connected spanner. A pair of nodes can form a direct link if they are within a bounded distance B of each other and the heights of towers at the two nodes are sufficient to achieve Line-of-Sight connectivity - i.e. the straight line connecting the top of the towers lies above any obstacles. In the planar setting where the obstacles are modeled as having a certain maximum height and minimum clearance distance, we give a constant factor approximation algorithm. In the case where the points lie on a 1.5-D terrain we illustrate that it might be hard to use Computational Geometry to achieve efficient approximations. The final problem we consider is the Multiway Barrier Cut problem. Here, given a set of points in the plane and a set of unit disk sensors also in the plane such that any path in the plane between any pair of input points hits at least one of the given sensor disks we consider the problem of finding the minimum size subset of these disks that still achieves this separation. We give a constant factor approximation algorithm for this problem.

We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios compared to the previously best-known deterministic on-line algorithms, which are (4+epsilon)-competitive in either case. Our preemptive algorithm is 2-competitive, which actually meets the competitive ratio of the currently best randomized on-line algorithm for this scenario. Our nonpreemptive algorithm has a competitive ratio of 3.28. Both results are characterized by a surprisingly simple analysis; moreover, the preemptive algorithm also works in the less clairvoyant environment in which only the ratio of weight to processing time of a job becomes known at its release date, but neither its actual weight nor its processing time. In the corresponding nonpreemptive situation, every on-line algorithm has an unbounded competitive ratio

This thesis is a survey on the approximability of the asymmetric traveling salesmanproblem with triangle inequality (ATSP).In the ATSP we are given a set of cities and a function that gives the cost of travelingbetween any pair of cities. The cost function must satisfy the triangle inequality, i.e.the cost of traveling from city A to city B cannot be larger than the cost of travelingfrom A to some other city C and then to B. However, we allow the cost function tobe asymmetric, i.e. the cost of traveling from city A to city B may not equal the costof traveling from B to A. The problem is then to find the cheapest tour that visit eachcity exactly once. This problem is NP-hard, and thus we are mainly interested in approximationalgorithms. We study the repeated cycle cover heuristic by Frieze et al. We alsostudy the Held-Karp heuristic, including the recent result by Asadpour et al. that givesa new upper bound on the integrality gap. Finally we present the result ofPapadimitriou and Vempala which shows that it is NP-hard to approximate the ATSP with a ratio better than 117/116.

The <i>mixed postman problem</i> consists of finding a minimum cost tour of a mixed graph <i>M</i> = (<i>V</i>,<i>E</i>,<i>A</i>) traversing all its edges and arcs at least once. We prove that two well-known linear programming relaxations of this problem are equivalent. The <i>extra cost</i> of a mixed postman tour <i>T</i> is the cost of <i>T</i> minus the cost of the edges and arcs of <i>M</i>. We prove that it is <i>NP</i>-hard to approximate the minimum extra cost of a mixed postman tour. A related problem, known as the <i>windy postman problem</i>, consists of finding a minimum cost tour of an undirected graph <i>G</i>=(<i>V</i>,<i>E</i>) traversing all its edges at least once, where the cost of an edge depends on the direction of traversal. We say that <i>G</i> is <i>windy postman perfect</i> if a certain <i>windy postman polyhedron O</i> (<i>G</i>) is integral. We prove that series-parallel undirected graphs are windy postman perfect, therefore solving a conjecture of Win. Given a mixed graph <i>M</i> = (<i>V</i>,<i>E</i>,<i>A</i>) and a subset <i>R</i> &#8838; <i>E</i> &#8746; <i>A</i>, we say that a mixed postman tour of <i>M</i> is <i>restricted</i> if it traverses the elements of <i>R</i> exactly once. The <i>restricted mixed postman problem</i> consists of finding a minimum cost restricted tour. We prove that this problem is <i>NP</i>-hard even if <i>R</i>=<i>A</i> and we restrict <i>M</i> to be planar, hence solving a conjecture of Veerasamy. We also prove that it is <i>NP</i>-complete to decide whether there exists a restricted tour even if <i>R</i>=<i>E</i> and we restrict <i>M</i> to be planar. The <i>edges postman problem</i> is the special case of the restricted mixed postman problem when <i>R</i>=<i>A</i>. We give a new class of valid inequalities for this problem. We introduce a relaxation of this problem, called the <i>b-join problem</i>, that can be solved in polynomial time. We give an algorithm which is simultaneously a 4/3-approximation algorithm for the edges postman problem, and a 2-approximation algorithm for the extra cost of a tour. The <i>arcs postman problem</i> is the special case of the restricted mixed postman problem when <i>R</i>=<i>E</i>. We introduce a class of necessary conditions for <i>M</i> to have an arcs postman tour, and we give a polynomial-time algorithm to decide whether one of these conditions holds. We give linear programming formulations of this problem for mixed graphs arising from windy postman perfect graphs, and mixed graphs whose arcs form a forest.

<p>This thesis explores how to sparsely represent distributions of points for geometric statistical problems. A <italic>coreset<italic> C is a small summary of a point set P such that if a certain statistic is computed on P and C, then the difference in the results is guaranteed to be bounded by a parameter &epsilon;. Two examples of coresets are &epsilon;-samples and &epsilon;-kernels. An &epsilon;-sample can estimate the density of a point set in any range from a geometric family of ranges (e.g., disks, axis-aligned rectangles). An &epsilon;-kernel approximates the width of a point set in all directions. Both coresets have size that depends only on &epsilon;, the error parameter, not the size of the original data set. We demonstrate several improvements to these coresets and how they are useful for geometric statistical problems.</p><p>We reduce the size of &epsilon;-samples for density queries in axis-aligned rectangles to nearly a square root of the size when the queries are with respect to more general families of shapes, such as disks. We also show how to construct &epsilon;-samples of probability distributions. </p><p>We show how to maintain &ldquo;stable&rdquo; &epsilon;-kernels, that is if the point set P changes by a small amount, then the &epsilon;-kernel also changes by a small amount. This is useful in surveillance tracking problems and the stable properties leads to more efficient algorithms for maintaining &epsilon;-kernels. </p><p>We next study when the input point sets are uncertain and their uncertainty is modeled by probability distributions. Statistics on these point sets (e.g., radius of smallest enclosing ball) do not have exact answers, but rather distributions of answers. We describe data structures to represent approximations of these distributions and algorithms to compute them. We also show how to create distributions of &epsilon;-kernels and &epsilon;-samples for these uncertain data sets. </p><p>Finally, we examine a spatial anomaly detection problem: computing a spatial scan statistic. The input is a point set P and measurements on the point set. The spatial scan statistic finds the range (e.g., an axis-aligned bounding box) where the measurements inside the range are the most different from measurements outside of the range. We show how to compute this statistic efficiently while allowing for a bounded amount of approximation error. This result generalizes to several statistical models and types of input point sets.</p> / Dissertation

<p>Large scale geometric data is ubiquitous. In this dissertation, we design algorithms and data structures to process large scale geometric data efficiently. We design algorithms for some fundamental geometric optimization problems that arise in motion planning, machine learning and computer vision.</p><p>For a stream S of n points in d-dimensional space, we develop (single-pass) streaming algorithms for maintaining extent measures such as the minimum enclosing ball and diameter. Our streaming algorithms have a work space that is polynomial in d and sub-linear in n. For problems of computing diameter, width and minimum enclosing ball of S, we obtain lower bounds on the worst-case approximation ratio of any streaming algorithm that uses polynomial in d space. On the positive side, we design a summary called the blurred ball cover and use it for answering approximate farthest-point queries and maintaining approximate minimum enclosing ball and diameter of S. We describe a streaming algorithm for maintaining a blurred ball cover whose working space is linear in d and independent</p><p>of n.</p><p>For a set P of k pairwise-disjoint convex obstacles in 3-dimensions, we design algorithms and data structures for computing Euclidean shortest path between source s and destination t. The running time of our algorithm is linear in n and the size and query time of our data structure is independent of n. We follow a summary based approach, i.e., quickly compute a small sketch Q of P whose size is independent of n and then compute approximate shortest paths with respect to Q.</p><p>For d-dimensional point sets A and B, |A| |B| n, and for a parameter &epsilon > 0,</p><p>We give an algorithm to compute &epsilon-approximate minimum weight perfect matching of A and B under d(. , .) in time O(n<super>1.5</super>&tau(n)) ; here &tau(n) is the query/update time of a dynamic weighted nearest neighbor under d(. , .). When A, B are point sets from</p><p>a bounded integer grid, for L₁ and L_infinity-norms, our algorithm computes minimum weight</p><p>perfect matching of A and B in time O(n<super>1.5</super>). Our algorithm also extends to a generalization of matching called the transportation problem.</p><p>We also present an O(n polylog n ) time algorithm that computes under any L_p-</p><p>norm, an &epsilon-approximate minimum weight perfect matching of A and B with high probability; all previous algorithms take </p><p>O(n<super>1.5</super> time. We approximate the L_p norm using a distance function, based on a randomly shifted quad-tree. The algorithm iteratively generates an approximate minimum-cost augmenting path under the new distance function in</p><p>time proportional to the length of the path. We show that the total length of the augmenting paths generated by the algorithm is O(n log n) implying a near-linear running time.</p><p>All the problems mentioned above have a history of more than two decades and algorithms presented here improve previous work by an order of magnitude. Many of these improvements are obtained by new geometric techniques that might have broader applications</p><p>and are of independent interest.</p> / Dissertation

No description available.

A recent line of works established a remarkable connection for antiferromagnetic 2-spin systems, including the Ising and hard-core models, showing that the computational complexity of approximating the partition function for graphs with maximum degree \Delta undergoes a computational transition that coincides with the statistical physics uniqueness/non-uniqueness phase transition on the infinite \Delta-regular tree. Despite this clear picture for 2-spin systems, there is little known for multi-spin systems. We present the first analog of the above inapproximability results for multi-spin systems. The main difficulty in previous inapproximability results was analyzing the behavior of the model on random \Delta-regular bipartite graphs, which served as the gadget in the reduction. To this end one needs to understand the moments of the partition function. Our key contribution is connecting: (i) induced matrix norms, (ii) maxima of the expectation of the partition function, and (iii) attractive fixed points of the associated tree recursions (belief propagation). We thus obtain a generic analysis of the Gibbs distribution of any multi-spin system on random regular bipartite graphs. We also treat in depth the k-colorings and the q-state antiferromagnetic Potts models. Based on these findings, we prove that for \Delta constant and even k<\Delta, it is NP-hard to approximate within an exponential factor the number of k-colorings on triangle-free \Delta-regular graphs. We also prove an analogous statement for the antiferromagnetic Potts model. Our hardness results for these models complement the conjectured regime where the models are believed to have efficient approximation schemes. We systematize the approach to obtain a general theorem for the computational hardness of counting in antiferromagnetic spin systems, which we ultimately use to obtain the inapproximability results for the k-colorings and q-state antiferromagnetic Potts models, as well as (the previously known results for) antiferromagnetic 2-spin systems. The criterion captures in an appropriate way the statistical physics uniqueness phase transition on the tree.

In the Directed Steiner Tree problem, we are given a directed graph G = (V,E) with edge costs, a root vertex r ∈ V, and a terminal set X ⊆ V . The goal is to find the cheapest subset of edges that contains an r-t path for every terminal t ∈ X. The only known polylogarithmic approximations for Directed Steiner Tree run in quasi-polynomial time and the best polynomial time approximations only achieve a guarantee of O(|X|^ε) for any constant ε > 0. Furthermore, the integrality gap of a natural LP relaxation can be as bad as Ω(√|X|).  We demonstrate that l rounds of the Sherali-Adams hierarchy suffice to reduce the integrality gap of a natural LP relaxation for Directed Steiner Tree in l-layered graphs from Ω( k) to O(l · log k) where k is the number of terminals. This is an improvement over Rothvoss’ result that 2l rounds of the considerably stronger Lasserre SDP hierarchy reduce the integrality gap of a similar formulation to O(l · log k). We also observe that Directed Steiner Tree instances with 3 layers of edges have only an O(logk) integrality gap bound in the standard LP relaxation, complementing the fact that the gap can be as large as Ω(√k) in graphs with 4 layers. Finally, we consider quasi-bipartite instances of Directed Steiner Tree meaning no edge in E connects two Steiner nodes V − (X ∪ {r}). By a simple reduction from Set Cover, it is still NP-hard to approximate quasi-bipartite instances within a ratio better than O(log|X|). We present a polynomial-time O(log |X|)-approximation for quasi-bipartite instances of Directed Steiner Tree. Our approach also bounds the integrality gap of the natural LP relaxation by the same quantity. A novel feature of our algorithm is that it is based on the primal-dual framework, which typically does not result in good approximations for network design problems in directed graphs.

Thesis (Ph.D.)--University of Nebraska-Lincoln, 2009. / Title from title screen (site viewed February 25, 2010). PDF text: x, 193 p. ; 3 Mb. UMI publication number: AAT 3386609. Includes bibliographical references. Also available in microfilm and microfiche formats.