Approximation Schemes for Planar Graph Problems
- PDF / 202,634 Bytes
- 4 Pages / 547.087 x 737.008 pts Page_size
- 20 Downloads / 245 Views
Open Problems Except for the NP-hardness, no other hardness results are known and it is possible that a polynomial-time algorithm with guarantee OPT + 1 exists for the problem. Resolving this is a key open question. A promising approach seems to be via the configuration LP (considered above). In fact, no instance is known for which the additive gap between the optimum configuration LP solution and the optimum integral solution is more than 1. It would be very interesting to design an instance that has an additive integrality gap of two or more. The OPT + O(log2 OPT) guarantee of Karmarkar and Karp has been the best known result for the last 25 years, and any improvement to this would be an extremely interesting result by itself. Cross References Bin Packing Knapsack Recommended Reading 1. Coffman, E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-hard Problems, pp. 46–93. PWS, Boston (1996) 2. Csirik, J., Woeginger, G.: On-line packing and covering problems. In: Fiat, A., Woeginger, G. (eds.) Online Algorithms: The State of the Art. LNCS, vol. 1442, pp. 147–177. Springer, Berlin (1998) 3. Fernandez de la Vega, W., Lueker, G.: Bin packing can be solved within 1 + " in linear time. Combinatorica 1, 349–355 (1981) 4. Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science (FOCS), 1982, pp. 312–320
Approximation Schemes for Planar Graph Problems 1983; Baker 1994; Baker ERIK D. DEMAINE1, MOHAMMADTAGHI HAJIAGHAYI 2 1 Computer Science and Artifical Intelligence Laboratory, MIT, Cambridge, MA, USA 2 Department of Computer Science, University of Pittsburgh, Pittsburgh, PA, USA Keywords and Synonyms Approximation algorithms in planar graphs; Baker’s approach; Lipton–Tarjan approach
A
Problem Definition Many NP-hard graph problems become easier to approximate on planar graphs and their generalizations. (A graph is planar if it can be drawn in the plane (or the sphere) without crossings. For definitions of other related graph classes, see the entry on bidimensionality (2004; Demaine, Fomin, Hajiaghayi, Thilikos).) For example, maximum independent set asks to find a maximum subset of vertices in a graph that induce no edges. This problem is inapproximable in general graphs within a factor of n1 for any > 0 unless NP = ZPP (and inapproximable within n1/2 unless P = NP), while for planar graphs there is a 4-approximation (or simple 5-approximation) by taking the largest color class in a vertex 4-coloring (or 5-coloring). Another is minimum dominating set, where the goal is to find a minimum subset of vertices such that every vertex is either in or adjacent to the subset. This problem is inapproximable in general graphs within log n for some > 0 unless P = NP, but as we will see, for planar graphs the problem admits a polynomial-time approximation scheme (PTAS): a collection of (1 + )-approximation alg
Data Loading...
