Abstract
We present some of the recent results on computational complexity of approximating bounded degree combinatorial optimization problems. In particular, we present the best up to now known explicit nonapproximability bounds on the very small degree optimization problems which are of particular importance on the intermediate stages of proving approximation hardness of some other generic optimization problems.
Supported in part by DFG grants, DIMACS, and IST grant 14036 (RAND-APX), and by the Max-Planck Research Prize. Research partially done while visiting Department of Computer Science, Yale University.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Arora, L. Babai, J. Stern and Z. Sweedyk, The Hardness of Approximate Optima in Lattice, Codes, and Systems of Linear Equations, Proc. of 34th IEEE FOCS, 1993, 724–733.
S. Arora, D. Karger, and M. Karpinski, Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems, Proc. 27th ACM STOC (1995), pp. 284–293; the full version appeared in J. Comput. System Sciences 58 (1999), pp. 193–210.
S. Arora and C. Lund, Hardness of Approximations, in Approximation Algorithms for NP-Hard Problems (D. Hochbaum, ed.), PWS Publ. Co. (1997), pp. 399–446.
S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof Verification and Hardness of Approximation Problems, Proc. 33rd IEEE FOCS (1992), pp. 14–20.
P. Berman and M. Fürer, Approximating Maximum Independent Set in Bounded Degree Graphs, Proc. 5th ACM-SIAM SODA (1994), pp. 365–371.
P. Berman and T. Fujito, Approximating independent sets in degree 3 graphs, Proc. 4th Workshop on Algorithms and Data Structures, LNCS Vol. 955, Springer-Verlag, 1995, pp. 449–460.
P. Berman, S. Hannenhalli and Karpinski, 1.375-Approximation Algorithm for Sorting by Reversals, Manuscript, 2001.
P. Berman and M. Karpinski, On Some Tighter Inapproximability Results, Proc. 26th ICALP (1999), LNCS 1644, Springer, 1999, pp. 200–209.
P. Berman and M. Karpinski, Approximating Minimum Unsatisfiability of Linear Equations, ECCC Technical Report TR01-025 (2001).
P. Berman and M. Karpinski, Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION, ECCC Technical Report TR01-026 (2001).
V. Bafna and P. Pevzner, Genome Rearrangements and Sorting by Reversals, SIAM J. on Computing 25 (1996), pp. 272–289.
A. Caprara Formulations and Hardness of Multiple Sorting by Reversals, Proc. ACM RECOMB’99, pp. 84–93.
I. Dinur, G. Kindler and S. Safra, Approximating CVP to Within Almost Polynomial Factors is NP-hard, Proc. of 39th IEEE FOCS, 1998, 99–109.
I. Dinur, G. Kindler, R. Raz and S. Safra, An Improved Lower Bound for Approximating CVP, 2000, submitted.
L. Engebretsen, An Explicit Lower Bound for TSP with Distances One and Two, Proc. 16th STACS (1999), LNCS 1563 (1999), Springer, 1999, pp. 371–382.
L. Engebretsen and M. Karpinski, Approximation Hardness of TSP with Bounded Metrics, ECCC Technical Report TR00-089 (2000), to appear in Proc. 28th ICALP (2001).
U. Feige, A Threshold of ln n for Approximation Set Cover, J. of ACM 45 (1998), pp. 634–652.
U. Feige and M. Goemans, Approximating the Value of Two Prover Proof Systems with Applications to MAX-2SAT and MAX-DICUT, Proc. 3rd Israel Symp. on Theory of Computing and Systems, 1995, pp. 182–189.
U. Feige and R. Krauthgamer, A Polylogarithmic Approximation of the Minimum Bisection, Proc. 41st IEEE FOCS (2000), pp. 105–115.
U. Feige, M. Karpinski, and M. Langberg, Improved Approximation of MAX-CUT on Graphs of Bounded Degree, ECCC Technical Report TR00-021 (2000), submitted to J. of Algorithms.
U. Feige, M. Karpinski, and M. Langberg, A Note on Approximation MAX-BISECTION on Regular Graphs, ECCC Technical Report TR00043 (2000), to appear in Information Processing Letters.
W. Fernandez de la Vega and M. Karpinski, On Approximation Hardness of Dense TSP and Other Path Problems, Information Processing Letters 70 (1999), pp. 53–55.
M. Goemans and D. Williamson, .878-approximation Algorithms for MAX-CUT and MAX2SAT, Proc. 26th ACM STOC (1994), pp. 422–431.
J. Håstad, Some Optimal Inapproximability Results, Proc. 29th ACM STOC (1997), pp. 1–10.
J. Håstad, On Bounded Occurrence Constraint Satisfaction, Information Processing Letters 74 (2000), pp. 1–6.
E. Halperin and U. Zwick, Improved Approximation Algorithms for Maximum Graph Bisection Problems, Manuscript, 2000.
K. Jansen, M. Karpinski, A. Lingas, and E. Seidel, Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs, Proc. 18th STACS (2001), LNCS 2010, Springer, 2001, pp. 365–375.
M. Karpinski, Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems, Algorithmica 30 (2001), pp. 386–397.
M. Karpinski, M. Kowaluk, and A. Lingas, Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs and Planar Graphs, ECCC Technical Report TR00-051 (2000).
M. Karpinski and A. Zelikovsky, Approximating Dense Cases of Covering Problems, ECCC Technical Report TR 97-004, 1997, also in Proc. DIMACS Workshop on Network Design: Connectivity and Facilities Location, Princeton, 1997, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 40 (1998), pp. 169–178.
S. Khanna, M. Sudan and L. Trevisan, Constraint Satisfaction: the approximability of minimization problems, Proc. of 12th IEEE Computational Complexity, 1997, 282–296.
C. Papadimitriou and M. Yannakakis, Optimization, Approximation and Complexity Classes, J. Comput. System Sciences 43 (1991), pp. 425–440.
C. H. Papadimitriou and M. Yannakakis, The Traveling Salesman Problem with Distances One and Two, Math. of Oper. Res. 18 (1993), pp. 1–11.
L. Trevisan, Non-approximability Results for Optimization Problems on Bounded Degree Instances, to appear in Proc. 33rd ACM STOC (2001).
S. Virhwanathan, An Approximation Algorithm for the Asymetric Travelling Salesman Problem with Distances One and Two, Information Processing Letters 44 (1992), pp. 297–302.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Karpinski, M. (2001). Approximating Bounded Degree Instances of NP-Hard Problems. In: Freivalds, R. (eds) Fundamentals of Computation Theory. FCT 2001. Lecture Notes in Computer Science, vol 2138. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44669-9_4
Download citation
DOI: https://doi.org/10.1007/3-540-44669-9_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42487-1
Online ISBN: 978-3-540-44669-9
eBook Packages: Springer Book Archive