Polynomial-time approximation schemes for piercing and covering with applications in wireless networks

Let be a set of disks of arbitrary radii in the plane, and let be a set of points. We study the following three problems: (i) Assuming contains the set of center points of disks in , find a minimum-cardinality subset of (if exists), such that each disk in is pierced by at least h points of , where h is a given constant. We call this problem minimum h-piercing. (ii) Assuming is such that for each there exists a point in whose distance from D's center is at most αr(D), where r(D) is D's radius and 0α<1 is a given constant, find a minimum-cardinality subset of , such that each disk in is pierced by at least one point of . We call this problem minimum discrete piercing with cores. (iii) Assuming is the set of center points of disks in , and that each covers at most l points of , where l is a constant, find a minimum-cardinality subset of , such that each point of is covered by at least one disk of . We call this problem minimum center covering. For each of these problems we present a constant-factor approximation algorithm (trivial for problem (iii)), followed by a polynomial-time approximation scheme. The polynomial-time approximation schemes are based on an adapted and extended version of Chan's [T.M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, J. Algorithms 46 (2003) 178–189] separator theorem. Our PTAS for problem (ii) enables one, in practical cases, to obtain a (1+ε)-approximation for minimum discrete piercing (i.e., for arbitrary ).     

Independent sets in bounded-degree hypergraphs

In this paper we analyze several approaches to the Maximum Independent Set (MIS) problem in hypergraphs with degree bounded by a parameter Δ. Since independent sets in hypergraphs can be strong and weak, we denote by MIS (MSIS) the problem of finding a maximum weak (strong) independent set in hypergraphs, respectively. We propose a general technique that reduces the worst case analysis of certain algorithms on hypergraphs to their analysis on ordinary graphs. This technique allows us to show that the greedy algorithm for MIS that corresponds to the classical greedy set cover algorithm has a performance ratio of (Δ+1)/2. It also allows us to apply results on local search algorithms on graphs to obtain a (Δ+1)/2 approximation for the weighted MIS and (Δ+3)/5−? approximation for the unweighted case. We improve the bound in the weighted case to ⌈(Δ+1)/3⌉ using a simple partitioning algorithm. We also consider another natural greedy algorithm for MIS that adds vertices of minimum degree and achieves only a ratio of Δ−1, significantly worse than on ordinary graphs. For MSIS, we give two variations of the basic greedy algorithm and describe a family of hypergraphs where both algorithms approach the bound of Δ.     

A local search approximation algorithm for k-means clustering

In k-means clustering we are given a set of n data points in d-dimensional space and an integer k, and the problem is to determine a set of k points in  , called centers, to minimize the mean squared distance from each data point to its nearest center. No exact polynomial-time algorithms are known for this problem. Although asymptotically efficient approximation algorithms exist, these algorithms are not practical due to the very high constant factors involved. There are many heuristics that are used in practice, but we know of no bounds on their performance.

We consider the question of whether there exists a simple and practical approximation algorithm for k-means clustering. We present a local improvement heuristic based on swapping centers in and out. We prove that this yields a (9+)-approximation algorithm. We present an example showing that any approach based on performing a fixed number of swaps achieves an approximation factor of at least (9−) in all sufficiently high dimensions. Thus, our approximation factor is almost tight for algorithms based on performing a fixed number of swaps. To establish the practical value of the heuristic, we present an empirical study that shows that, when combined with Lloyd's algorithm, this heuristic performs quite well in practice.     

Continuous approximation schemes for stochastic programs

One of the main methods for solving stochastic programs is approximation by discretizing the probability distribution. However, discretization may lose differentiability of expectational functionals. The complexity of discrete approximation schemes also increases exponentially as the dimension of the random vector increases. On the other hand, stochastic methods can solve stochastic programs with larger dimensions but their convergence is in the sense of probability one. In this paper, we study the differentiability property of stochastic two-stage programs and discuss continuous approximation methods for stochastic programs. We present several ways to calculate and estimate this derivative. We then design several continuous approximation schemes and study their convergence behavior and implementation. The methods include several types of truncation approximation, lower dimensional approximation and limited basis approximation.His work is supported by Office of Naval Research Grant N0014-86-K-0628 and the National Science Foundation under Grant ECS-8815101 and DDM-9215921.His work is supported by the Australian Research Council.     

Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms

Using ideas and results from polynomial time approximation and exact computation we design approximation algorithms for several NP-hard combinatorial problems achieving ratios that cannot be achieved in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation. We study in particular two paradigmatic problems, max independent set and min vertex cover.     

An approximation algorithm for maximum triangle packing

We present a randomized -approximation algorithm for the weighted maximum triangle packing problem, for any given ε>0. This is the first algorithm for this problem whose performance guarantee is better than . The algorithm also improves the best-known approximation bound for the maximum 2-edge path packing problem.     

An optimal adaptive algorithm for the approximation of concave functions

Motivated by the study of parametric convex programs, we consider approximation of concave functions by piecewise affine functions. Using dynamic programming, we derive a procedure for selecting the knots at which an oracle provides the function value and one supergradient. The procedure is adaptive in that the choice of a knot is dependent on the choice of the previous knots. It is also optimal in that the approximation error, in the integral sense, is minimized in the worst case. This work was partially supported by NSERC (Canada) and FCAR (Québec).     

An improved approximation algorithm for maximum edge 2-coloring in simple graphs

We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of $\frac{468}{575}$. This improves on the previous best (trivial) ratio of $\frac{4}{5}$.     

Approximation algorithms for art gallery problems in polygons

In this paper, we present approximation algorithms for minimum vertex and edge guard problems for polygons with or without holes with a total of n vertices. For simple polygons, approximation algorithms for both problems run in O(n⁴) time and yield solutions that can be at most O(logn) times the optimal solution. For polygons with holes, approximation algorithms for both problems give the same approximation ratio of O(logn), but the running time of the algorithms increases by a factor of n to O(n⁵).     

经典一维装箱问题近似算法的研究进展

自20世纪70年代开始,随着计算复杂性理论的建立,近似算法逐渐成为组合优化的重要研究方向。作为第一批研究对象,装箱问题引起了组合优化领域学者的极大关注。装箱问题模型简单、拓展性强,广泛出现在各种带容量约束的资源分配问题中。除了在物流装载和材料切割等方面愈来愈重要的应用外,装箱算法的任何理论突破都关乎到整个组合优化领域的发展。直到今天,对装箱问题近似算法的研究仍如火如荼。本文主要针对一维模型,简述若干经典Fit算法的发展历程,分析基于线性规划松弛的近似方案的主要思路,总结当前的研究现状并对未来的研究提供一些参考建议。     

经典一维装箱问题近似算法的研究进展

自20世纪70年代开始,随着计算复杂性理论的建立,近似算法逐渐成为组合优化的重要研究方向。作为第一批研究对象,装箱问题引起了组合优化领域学者的极大关注。装箱问题模型简单、拓展性强,广泛出现在各种带容量约束的资源分配问题中。除了在物流装载和材料切割等方面愈来愈重要的应用外,装箱算法的任何理论突破都关乎到整个组合优化领域的发展。直到今天,对装箱问题近似算法的研究仍如火如荼。本文主要针对一维模型,简述若干经典Fit算法的发展历程,分析基于线性规划松弛的近似方案的主要思路,总结当前的研究现状并对未来的研究提供一些参考建议。     

A PTAS for the disk cover problem of geometric objects

We present PTASs for the disk cover problem: given geometric objects and a finite set of disk centers, minimize the total cost for covering those objects with disks under a polynomial cost function on the disks’ radii. We describe the first FPTAS for covering a line segment when the disk centers form a discrete set, and a PTAS for when a set of geometric objects, described by polynomial algebraic inequalities, must be covered. The latter result holds for any dimension.     

Sums of squares based approximation algorithms for MAX-SAT

We investigate the Semidefinite Programming based sums of squares (SOS) decomposition method, designed for global optimization of polynomials, in the context of the (Maximum) Satisfiability problem. To be specific, we examine the potential of this theory for providing tests for unsatisfiability and providing MAX-SAT upper bounds. We compare the SOS approach with existing upper bound and rounding techniques for the MAX-2-SAT case of Goemans and Williamson [Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42(6) (1995) 1115-1145] and Feige and Goemans [Approximating the value of two prover proof systems, with applications to MAX2SAT and MAXDICUT, in: Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995, pp. 182-189] and the MAX-3-SAT case of Karloff and Zwick [A 7/8-approximation algorithm for MAX 3SAT? in: Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, Miami Beach, FL, USA, IEEE Press, New York, 1997], which are based on Semidefinite Programming as well. We prove that for each of these algorithms there is an SOS-based counterpart which provides upper bounds at least as tight, but observably tighter in particular cases. Also, we propose a new randomized rounding technique based on the optimal solution of the SOS Semidefinite Program (SDP) which we experimentally compare with the appropriate existing rounding techniques. Further we investigate the implications to the decision variant SAT and compare experimental results with those yielded from the higher lifting approach of Anjos [On semidefinite programming relaxations for the satisfiability problem, Math. Methods Oper. Res. 60(3) (2004) 349-367; An improved semidefinite programming relaxation for the satisfiability problem, Math. Programming 102(3) (2005) 589-608; Semidefinite optimization approaches for satisfiability and maximum-satisfiability problems, J. Satisfiability Boolean Modeling Comput. 1 (2005) 1-47].We give some impression of the fraction of the so-called unit constraints in the various SDP relaxations. From a mathematical viewpoint these constraints should be easily dealt within an algorithmic setting, but seem hard to be avoided as extra constraints in an SDP setting. Finally, we briefly indicate whether this work could have implications in finding counterexamples to uncovered cases in Hilbert's Positivstellensatz.     

Distributed algorithms for weighted problems in sparse graphs

We study distributed algorithms for three graph-theoretic problems in weighted trees and weighted planar graphs. For trees, we present an efficient deterministic distributed algorithm which finds an almost exact approximation of a maximum-weight matching. In addition, in the case of trees, we show how to approximately solve the minimum-weight dominating set problem. For planar graphs, we present an almost exact approximation for the maximum-weight independent set problem.     

On the approximability of the Maximum Agreement SubTree and Maximum Compatible Tree problems

The aim of this paper is to give a complete picture of approximability for two tree consensus problems which are of particular interest in computational biology: Maximum Agreement SubTree (MAST) and Maximum Compatible Tree (MCT). Both problems take as input a label set and a collection of trees whose leaf sets are each bijectively labeled with the label set. Define the size of a tree as the number of its leaves. The well-known MAST problem consists of finding a maximum-sized tree that is topologically embedded in each input tree, under label-preserving embeddings. Its variant MCT is less stringent, as it allows the input trees to be arbitrarily refined. Our results are as follows. We show that MCT is -hard to approximate within bound n^1−? on rooted trees, where n denotes the size of each input tree; the same approximation lower bound was already known for MAST [J. Jansson, Consensus algorithms for trees and strings, Ph. D. Thesis, Lund University, 2003]. Furthermore, we prove that MCT on two rooted trees is not approximable within bound 2^log1−?n, unless all problems in are solvable in quasi-polynomial time; the same result was previously established for MAST on three rooted trees [J. Hein, T. Jiang, L. Wang, K. Zhang, On the complexity of comparing evolutionary trees, Discrete Applied Mathematics 71 (1-3) (1996) 153-169] (note that MAST on two trees is solvable in polynomial time [M.A. Steel, T.J. Warnow, Kaikoura tree theorems: Computing the maximum agreement subtree, Information Processing Letters 48 (2) (1993) 77-82]). Let CMAST, resp. CMCT, denote the complement version of MAST, resp. MCT: CMAST, resp. CMCT, consists of finding a tree that is a feasible solution of MAST, resp. MCT, and whose leaf label set excludes a smallest subset of the input labels. The approximation threshold for CMAST, resp. CMCT, on rooted trees is shown to be the same as the approximation threshold for CMAST, resp. CMCT, on unrooted trees; it was already known that both CMAST and CMCT are approximable within ratio three on rooted and unrooted trees [V. Berry, F. Nicolas, Maximum agreement and compatible supertrees, in: S.C. Sahinalp, S. Muthukrishnan, U. Dogrusoz (Eds.), Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, CPM’04, in: LNCS, vol. 3109, Springer-Verlag, 2004, pp. 205-219; G. Ganapathy, T.J. Warnow, Approximating the complement of the maximum compatible subset of leaves of k trees, in: K. Jansen, S. Leonardi, V. V. Vazirani (Eds.), Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX’02, in: LNCS, vol. 2462, Springer-Verlag, 2002, pp. 122-134]. The latter results are completed by showing that CMAST is -hard on three rooted trees and that CMCT is -hard on two rooted trees.     

Optimization problems in multiple subtree graphs

We study various optimization problems in t-subtree graphs, the intersection graphs of t-subtrees, where a t-subtree is the union of t disjoint subtrees of some tree. This graph class generalizes both the class of chordal graphs and the class of t-interval graphs, a generalization of interval graphs that has recently been studied from a combinatorial optimization point of view. We present approximation algorithms for the Maximum Independent Set, Minimum Coloring, Minimum Vertex Cover, Minimum Dominating Set, and Maximum Clique problems.     

Dynamic data structures for fat objects and their applications

We present several efficient dynamic data structures for point-enclosure queries, involving convex fat objects in or. Our planar structures are actually fitted for a more general class of objects – (β,δ)-covered objects – which are not necessarily convex, see definition below. These structures are more efficient than alternative known structures, because they exploit the fatness of the objects. We then apply these structures to obtain efficient solutions to two problems: (i) finding a perfect containment matching between a set of points and a set of convex fat objects, and (ii) finding a piercing set for a collection of convex fat objects, whose size is optimal up to some constant factor.