×

The inapproximability of non-NP-hard optimization problems. (English) Zbl 1061.68059

Summary: The inapproximability of non-NP-hard optimization problems is investigated. Techniques are given to show that the problems LOG DOMINATING SET and LOG HYPERGRAPH VERTEX COVER cannot be approximated to a constant ratio in polynomial time unless the corresponding NP-hard versions are also approximable in deterministic subexponential time. A direct connection is established between non-NP-hard problems and a PCP characterization of NP. Reductions from the PCP characterization show that LOG CLIQUE is not approximable in polynomial time and MAX SPARSE SAT does not have a FPTAS under the assumption that NP\(\nsubseteq\)DTIME\((2^{O(n \log n)})\). A number of nontrivial approximation-preserving reductions are also presented, making it possible to extend inapproximability results to more natural non-NP-hard problems such as TOURNAMENT DOMINATING SET and RICH HYPERGRAPH VERTEX COVER.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
90C60 Abstract computational complexity for mathematical programming problems
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Arora, Personal communication.; S. Arora, Personal communication.
[2] Arora, S.; Lund, C., Hardness of approximations, (Hochbaum, D., Approximation Algorithms for NP-hard problems (1997), PWS Publishing: PWS Publishing Boston), 399-446
[3] S. Arora, C. Lund, R. Motwani, M. Sundar, M. Szegedy, Verification and hardness of approximation problems, in: Proc. 33rd Ann. IEEE Symp. on Foundations of Computer Science, Los Alamitos, CA, IEEE Computer Society Press, Silver Spring, MD, 1992, pp. 14-23.; S. Arora, C. Lund, R. Motwani, M. Sundar, M. Szegedy, Verification and hardness of approximation problems, in: Proc. 33rd Ann. IEEE Symp. on Foundations of Computer Science, Los Alamitos, CA, IEEE Computer Society Press, Silver Spring, MD, 1992, pp. 14-23. · Zbl 0977.68539
[4] S. Arora, S. Safra, Probabilistic checking of proofs, in: Proc. 33rd Ann. Symp. on Foundations of Computer Science, IEEE Computer Society Press, Silver Spring, MD, 1992, pp. 2-13.; S. Arora, S. Safra, Probabilistic checking of proofs, in: Proc. 33rd Ann. Symp. on Foundations of Computer Science, IEEE Computer Society Press, Silver Spring, MD, 1992, pp. 2-13. · Zbl 0945.68516
[5] Ausiello, G.; Crescenzi, P.; Gambosi, G.; Kann, V.; Marchetti Spaccamela, A.; Protasi, M., Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties (1999), Springer: Springer Berlin · Zbl 0937.68002
[6] M. Bellare, S. Goldwasser, C. Lund, A. Russell, Efficient probabilistic checking of proofs and applications to approximation, in: Proc. 25th Ann. ACM Symp. on the Theory of Computing, New York, 1993, ACM Press, New York, pp. 294-304.; M. Bellare, S. Goldwasser, C. Lund, A. Russell, Efficient probabilistic checking of proofs and applications to approximation, in: Proc. 25th Ann. ACM Symp. on the Theory of Computing, New York, 1993, ACM Press, New York, pp. 294-304. · Zbl 1310.68083
[7] Boppana, R.; Halldórsson, M. M., Approximating maximum independent sets by excluding subgraphs, BIT, 32, 180-196 (1992) · Zbl 0761.68044
[8] Buss, J. F.; Goldsmith, J., Nondeterminism within P, SIAM J. Comput., 22, 560-572 (1993) · Zbl 0773.68031
[9] Cai, L.; Chen, J., On fixed-parameter tractability and approximability of NP optimization problems, J. Comput. System Sci., 54, 3, 465-474 (1997) · Zbl 0882.68064
[10] Cai, L.; Chen, J., On the amount of nondeterminism and the power of verifier, SIAM J. Comput., 26, 3, 733-750 (1997) · Zbl 0870.68062
[11] Cai, L.; Chen, J.; Downey, R.; Fellows, M., On the structure of parameterized problems in NP, Inform. Comput., 123, 38-49 (1995) · Zbl 1096.68626
[12] Dı́az, J.; Torán, J., Classes of bounded nondeterminism, Math. System Theory, 23, 21-32 (1990) · Zbl 0692.68029
[13] R.G. Downey, M.R. Fellows, Fixed-parameter intractability, in: Proc. Seventh Ann. Conf. Structure in Complexity Theory, Boston, MA, USA, IEEE Computer Society Press, Silver Spring, MD, 1992, pp. 36-49.; R.G. Downey, M.R. Fellows, Fixed-parameter intractability, in: Proc. Seventh Ann. Conf. Structure in Complexity Theory, Boston, MA, USA, IEEE Computer Society Press, Silver Spring, MD, 1992, pp. 36-49.
[14] Downey, R. G.; Fellows, M. R., Fixed-parameter tractability and completeness I: Basic results, SIAM J. Comput., 24, 4, 873-921 (1995) · Zbl 0830.68063
[15] R.G. Downey, M.R. Fellows, Parameterized computational feasibility, in: FEASMATH: Feasible Mathematics: A Mathematical Sciences Institute Workshop, Birkhauser, 1995.; R.G. Downey, M.R. Fellows, Parameterized computational feasibility, in: FEASMATH: Feasible Mathematics: A Mathematical Sciences Institute Workshop, Birkhauser, 1995. · Zbl 0834.68046
[16] Farr, G., On problems with short certificates, Acta Inform., 31, 479-502 (1994) · Zbl 0818.68075
[17] U. Feige, S. Goldwasser, L. Lovász, S. Safra, M. Szegedy, Approximating clique is almost NP-complete, in: Proc. 32nd IEEE Symp. on the Foundations of Computer Science, IEEE Computer Society Press, Silver Spring, MD, 1991, pp. 2-12.; U. Feige, S. Goldwasser, L. Lovász, S. Safra, M. Szegedy, Approximating clique is almost NP-complete, in: Proc. 32nd IEEE Symp. on the Foundations of Computer Science, IEEE Computer Society Press, Silver Spring, MD, 1991, pp. 2-12.
[18] Feige, U.; Kilian, J., On limited versus polynomial nondeterminism, Chicago J. Theoret. Comput. Sci., 1997, 1-20 (1997) · Zbl 0924.68080
[19] U. Feige, A threshold of \(ln\); U. Feige, A threshold of \(ln\)
[20] D. Fotakis, P. Spirakis, (poly \(( log log\); D. Fotakis, P. Spirakis, (poly \(( log log\) · Zbl 0889.68059
[21] Goldsmith, J.; Levy, M.; Mundhenk, M., Guest column: Limited nondeterminism, SIGACT News, 27, 2, 20-29 (1996)
[22] Johnson, D. S., Approximation algorithms for combinatorial problems, J. Comput. Systems Sci., 9, 256-278 (1974) · Zbl 0296.65036
[23] V. Kann, On the Approximability of NP-complete Optimization Problems, Ph.D. Thesis, Royal Institute of Technology, Sweden, 1992.; V. Kann, On the Approximability of NP-complete Optimization Problems, Ph.D. Thesis, Royal Institute of Technology, Sweden, 1992.
[24] Megiddo, N.; Vishkin, U., On finding a minimum dominating set in a tournament, Theoret. Comput. Sci., 61, 307-316 (1988) · Zbl 0661.68064
[25] C.H. Papadimitriou, M. Yannakakis, On limited nondeterminism and the complexity of the V-C dimension, in: Proc. Eigth Ann. Conf. on Structure in Complexity Theory (SCTC ’93), San Diego, CA, USA, IEEE Computer Society Press, Silver Spring, MD, 1993, pp. 12-18.; C.H. Papadimitriou, M. Yannakakis, On limited nondeterminism and the complexity of the V-C dimension, in: Proc. Eigth Ann. Conf. on Structure in Complexity Theory (SCTC ’93), San Diego, CA, USA, IEEE Computer Society Press, Silver Spring, MD, 1993, pp. 12-18.
[26] J. Håstad, Clique is hard to approximate within \(n^{1−ε}\); J. Håstad, Clique is hard to approximate within \(n^{1−ε}\)
[27] R. Szelepcsényi, \(βk\); R. Szelepcsényi, \(βk\)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.