Efficient approximation of combinatorial problems by moderately exponential algorithms. (English) Zbl 1253.68357
Dehne, Frank (ed.) et al., Algorithms and data structures. 11th international symposium, WADS 2009, Banff, Canada, August 21–23, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03366-7/pbk). Lecture Notes in Computer Science 5664, 507-518 (2009).
Summary: 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 Max Independent Set, Min Vertex Cover and Min Set Cover and then extend our results to Max Clique, Max Bipartite Subgraph and Max Set Packing.
For the entire collection see [Zbl 1173.68007].
For the entire collection see [Zbl 1173.68007].
References:
| [1] | Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. In: Jünger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol. 2570, pp. 185–207. Springer, Heidelberg (2003) · Zbl 1024.68529 · doi:10.1007/3-540-36478-1_17 |
| [2] | Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and approximation. In: Combinatorial optimization problems and their approximability properties. Springer, Berlin (1999) · Zbl 0937.68002 |
| [3] | Hochbaum, D.S. (ed.): Approximation algorithms for NP-hard problems. PWS, Boston (1997) · Zbl 1368.68010 |
| [4] | Vazirani, V.: Approximation algorithms. Springer, Berlin (2001) · Zbl 0999.68546 |
| [5] | Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and intractability of approximation problems. J. Assoc. Comput. Mach. 45, 501–555 (1998) · Zbl 1065.68570 · doi:10.1145/278298.278306 |
| [6] | Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proc. STOC 2006, pp. 681–690 (2006) · Zbl 1301.68152 · doi:10.1145/1132516.1132612 |
| [7] | Björklund, A., Husfeldt, T.: Inclusion-exclusion algorithms for counting set partitions. In: Proc. FOCS 2006, pp. 575–582 (2006) · doi:10.1109/FOCS.2006.41 |
| [8] | Cygan, M., Kowalik, L., Pilipczuk, M., Wykurz, M.: Exponential-time approximation of hard problems. arXiv:0810.4934v1 (2008), http://arxiv.org/abs/0810.4934v1 |
| [9] | Cai, L., Huang, X.: Fixed-parameter approximation: conceptual framework and approximability results. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 96–108. Springer, Heidelberg (2006) · Zbl 1154.68570 · doi:10.1007/11847250_9 |
| [10] | Chen, Y., Grohe, M., Grüber, M.: On parameterized approximability. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 109–120. Springer, Heidelberg (2006) · Zbl 1154.68571 · doi:10.1007/11847250_10 |
| [11] | Downey, R.G., Fellows, M.R., McCartin, C.: Parameterized approximation problems. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 121–129. Springer, Heidelberg (2006) · Zbl 1154.68572 · doi:10.1007/11847250_11 |
| [12] | Vassilevska, V., Williams, R., Woo, S.: Confronting hardness using a hybrid approach. In: Proc. Symposium on Discrete Algorithms, SODA 2006, pp. 1–10 (2006) · Zbl 1192.68381 · doi:10.1145/1109557.1109558 |
| [13] | Bourgeois, N., Escoffier, B., Paschos, V.T.: Efficient approximation by ”low-complexity” exponential algorithms. Cahier du LAMSADE 271, LAMSADE, Université Paris-Dauphine (2007), http://www.lamsade.dauphine.fr/cahiers/PDF/cahierLamsade271.pdf · Zbl 1166.68043 |
| [14] | Bourgeois, N., Escoffier, B., Paschos, V.T.: Efficient approximation of min set cover by ”low-complexity” exponential algorithms. Cahier du LAMSADE 278, LAMSADE, Université Paris-Dauphine (2008), http://www.lamsade.dauphine.fr/cahiers/PDF/cahierLamsade278.pdf · Zbl 1166.68043 |
| [15] | Robson, J.M.: Finding a maximum independent set in time O(2n/4). Technical Report 1251-01, LaBRI, Université de Bordeaux I (2001) |
| [16] | Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2 - {\(\epsilon\)}. In: Proc. Annual Conference on Computational Complexity, CCC 2003, pp. 379–386 (2003) · doi:10.1109/CCC.2003.1214437 |
| [17] | Chen, J., Kanj, I., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms 41, 280–301 (2001) · Zbl 1017.68087 · doi:10.1006/jagm.2001.1186 |
| [18] | Nemhauser, G.L., Trotter, L.E.: Vertex packings: structural properties and algorithms. Math. Programming 8, 232–248 (1975) · Zbl 0314.90059 · doi:10.1007/BF01580444 |
| [19] | Berman, P., Fujito, T.: On the approximation properties of independent set problem in degree 3 graphs. In: Sack, J.-R., Akl, S.G., Dehne, F., Santoro, N. (eds.) WADS 1995. LNCS, vol. 955, pp. 449–460. Springer, Heidelberg (1995) · doi:10.1007/3-540-60220-8_84 |
| [20] | Duh, R., Fürer, M.: Approximation of k-set cover by semi-local optimization. In: Proc. STOC 1997, pp. 256–265 (1997) · Zbl 0962.68172 · doi:10.1145/258533.258599 |
| [21] | van Rooij, J., Bodlaender, H.: Design by measure and conquer, a faster exact algorithm for dominating set. In: Albers, S., Weil, P. (eds.) Proc. International Symposium on Theoretical Aspects of Computer Science, STACS 2008, pp. 657–668 (2008) · Zbl 1259.68097 |
| [22] | Björklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput. (To appear in the special issue dedicated to selected papers from FOCS 2006) · Zbl 1215.05056 |
| [23] | Simon, H.U.: On approximate solutions for combinatorial optimization problems. SIAM J. Disc. Math. 3, 294–310 (1990) · Zbl 0699.68077 · doi:10.1137/0403025 |
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.
