Abstract
The class P consists of all polynomial-time solvable decision problems. What is the class NP? There are two popular misunderstandings:
-
(1)
NP is the class of problems which are not polynomial-time solvable.
-
(2)
A decision problem belongs to the class NP if its answer can be checked in polynomial-time.
The biggest difference between time and space is that you can’t reuse time.
—Merrick Furst
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
If they are rational numbers, then we can transform them into integers. If some of them are irrational numbers, then we have to touch the complexity theory of real number computation, which is out of scope of this book.
- 2.
Theorem 8.3.9 states for undirected graphs. The same theorem also holds for directed graphs since the graph can be seen as special case of directed graphs.
References
S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy: Proof verification and hardness of approximation problems, Proceedings, 33rd IEEE Symposium on Foundations of Computer Science, pp. 14–23, 1992.
S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy: Proof verification and hardness of approximation problems, Journal of the ACM, 45: 753–782 (1998).
S. Arora and S. Safra: Probabilistic checking of proofs: A new characterization of NP, Proceedings, 33rd IEEE Symposium on Foundations of Computer Science, pp. 2–13, 1992.
S. Arora and S. Safra: Probabilistic checking of proofs: A new characterization of NP, J. Assoc. Comput. Mach., 45: 70–122 (1998).
Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige: Aravindan vijayaraghavan: detecting high log-densities – an O(n 1∕4) approximation for densest k-subgraph, Proceedings, 42nd ACM International Symposium on Theory of Computing, ACM, New York, pp. 201–210, 2010.
M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha and M. Li: Approximation algorithms for directed Steiner problems, Journal of Algorithms, 33: 73–91 (1999).
N. Christofides: Worst-case analysis of a new heuristic for the travelling salesman problem, Technical Report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976.
S.A. Cook: The complexity of theorem-proving procedures, Proceedings, 3rd ACM Symposium on Theory of Computing, pp. 151–158, 1971.
Ding-Zhu Du, Ker-I Ko, Xiaodong Hu: Design and Analysis of Approximation Algorithms, (Springer, 2012).
Uriel Feige: A threshold of \(\ln n\) for approximating set cover, J. ACM, 45(4): 634–652 (1998).
M.R. Garey and D.S. Johnson: The complexity of near-optimal graph coloring, J. Assoc. Comput. Mach., 23: 43–49 (1976).
M.R. Garey and D.S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness, (W. H. Freeman and Company, New York, 1979).
N. Garg, G. Konjevod, R. Ravi, A polylogarithmic approximation algorithm for the group Steiner tree problem, Proceedings, 9th SODA, vol. 95, p. 253, 1998.
R.L. Graham: Bounds on multiprocessing timing anomalies, Bell System Tech. J., 45: 1563–1581 (1966).
E. Halperin, R. Krauthgamer: Polylogarithmic inapproximability, Proceedings, 35th ACM Symposium on Theory of Computing, pp. 585–594, 2003.
J. Hastad: Clique is hard to approximate within n to the power 1 − ε, Acta Math., 182: 105–142 (1999).
J. Hastad: Some optimal inapproximability results, J. Assoc. Comput. Mach., 48: 798–859 (2001).
O.H. Ibarra and C.E. Kim: Fast approximation algorithms for the knapsack and sum of subset proble, J. Assoc. Comput. Mach., 22: 463–468 (1975).
R.M. Karp: Reducibility among combinatorial problems, in Complexity of Computer Computations, (E.E. Miller and J.W. Thatcher eds.), Plenum Press, New York, pp. 85–103, 1972.
S. Khanna, R. Motwani, M. Sudan and U. Vazirani: On syntactic versus computational views of approximability, SIAM J. Comput., 28: 164–191 (1999).
Ker-I Ko: Computational Complexity of Real Functions and Polynomial Time Approximation, Ph.D. Thesis, Ohio State University, Columbus, Ohio, 1979.
Zaixin Lu, Wei Zhang, Weili Wu, Joonmo Kim, Bin Fu: The complexity of influence maximization problem in the deterministic linear threshold model, J. Comb. Optim., 24(3): 374–378 (2012).
Zaixin Lu, Wei Zhang, Weili Wu, Bin Fu, Ding-Zhu Du: Approximation and inapproximation for the influence maximization problem in social networks under deterministic linear threshold model, ICDCS Workshops, pp. 160–165, 2011.
Zaixin Lu, Zhao Zhang, Weili Wu: Solution of Bharathi-Kempe-Salek conjecture for influence maximization on arborescence, J. Comb. Optim., 33(2): 803–808 (2017).
C. Lund, M. Yanakakis: On the hardness of approximating minimization problems, J. ACM, 41(5): 960–981 (1994).
C. Papadimitriou and M. Yannakakis: Optimization, approximations, and complexity classes, Proceedings, 20th ACM Symposium on Theory of Computing, pp. 229–234, 1988.
R. Raz and S. Safra: A sub-constant error-probability low-degree test, and a subconstant error-probability PCP characterization of NP, Proceedings, 28th ACM Symposium on Theory of Computing, pp. 474–484, 1997.
S. Sahni: Approximate algorithms for the 0/1 knapsack problem, J. Assoc. Comput. Mach., 22: 115–124 (1975).
S. Sahni and T. Gonzalez: P-complete approximation algorithms, J. Assoc. Comput. Mach., 23: 555–565 (1976).
Wei Zhang, Weili Wu, Wonjun Lee, Ding-Zhu Du: Complexity and approximation of the connected set-cover problem, J. Glob. Optim., 53(3): 563–572 (2012).
Zhao Zhang, Weili Wu, Jing Yuan, Ding-Zhu Du: Breach-free sleep-wakeup scheduling for barrier coverage with heterogeneous wireless sensors, IEEE/ACM Trans. Netw., 26(5): 2404–2413 (2018).
D. Zuckerman: Linear degree extractors and the inapproximability of max clique and chromatic number, Proceedings, 38th ACM Symposium on Theory of Computing, pp. 681–690, 2006.
D. Zuckerman: Linear degree extractors and the inapproximability of Max Clique and Chromatic Number, Theory Comput., 3: 103–128 (2007).
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Cite this chapter
Du, DZ., Pardalos, P., Hu, X., Wu, W. (2022). NP-Hard Problems and Approximation Algorithms. In: Introduction to Combinatorial Optimization. Springer Optimization and Its Applications, vol 196. Springer, Cham. https://doi.org/10.1007/978-3-031-10596-8_8
Download citation
DOI: https://doi.org/10.1007/978-3-031-10596-8_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-10594-4
Online ISBN: 978-3-031-10596-8
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)