Probabilistic approximate algorithms in discrete optimization

N. N. Kuzyurin

Diskretnyj analiz i issledovanie operacij, Tome 9 (2002) no. 2, pp. 97-114.

Bibliographie

[1] Kostochka A. V., Serdyukov A. I., “Polinomialnye algoritmy s otsenkami 3/4 i 5/6 dlya zadachi kommivoyazhera na maksimum”, Upravlyaemye sistemy, Sb. nauch. tr., no. 26, In-t matematiki SO AN SSSR, Novosibirsk, 1985, 55–59 | MR

[2] Kuzyurin N. N., “Asimptoticheski tochnye polinomialnye algoritmy v tselochislennom lineinom programmirovanii”, Diskret. matematika, 1:2 (1989), 78–85 | MR | Zbl

[3] Serdyukov A. I., “Algoritm s otsenkoi dlya zadachi kommivoyazhera na maksimum”, Upravlyaemye sistemy, Sb. nauch. tr., no. 25, In-t matematiki SO AN SSSR, Novosibirsk, 1984, 80–86 | MR

[4] Ageev A. A., Sviridenko M. I., “Approximation algorithms for maximum coverage and MAX CUT with given sizes of parts”, Integer programming and combinatorial optimization (Graz, 1999), Lecture Notes in Comput. Sci., 1610, Springer, Berlin, 1999, 17–30 | MR | Zbl

[5] Ageev A. A., Sviridenko M. I., “An $0{.}828$-approximation algorithm for the uncapacitated facility location problem”, Discrete Appl. Math., 93:2–3 (1999), 149–156 | DOI | MR | Zbl

[6] Arora S., “Polynomial time approximation schemes for Euclidean TSP and other geometric problems”, Proc. of the 37th annual symposium on foundations of computer science, IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, 2–11 | MR

[7] Arora S., Karger D., Karpinski M., “Polynomial time approximation schemes for dense instances of NP-hard problems”, Proc. of the 27th annual ACM symposium on theory of computing, ACM Press, New York, 1995, 284–293 | Zbl

[8] Asano T., Ono T., Hirata T., “Approximation algorithms for the maximum satifiability problem”, Nordic J. Comput., 3:4 (1996), 388–404 | MR | Zbl

[9] Asano T., Williamson D. P., “Improved approximation algorithms for MAX SAT”, Proc. of the 11th ACM-SIAM simposium on discrete algorithms, SIAM, Philadelphia, 2000, 96–105 | MR | Zbl

[10] Asratian A., Kuzjurin N., Optima of generalized covering programs, Research Rep. 1999-07. Lulea Univ. | MR

[11] Bertsimas D., Vohra R., “Rounding algorithms for covering problems”, Math. Programming, 80:1 (1998), 63–89 | DOI | MR | Zbl

[12] Chekuri C., Khanna S., “On multi-dimensional packing problems”, Proc. of the 10th annual ACM-SIAM symposium on discrete algorithms, ACM Press, New York, 1999, 185–194 | MR | Zbl

[13] Christofides N., Worst-case analysis of a new heuristic for the traveling salesman problem, Techn. Rep. CS-93-13, Carnegie Mellon Univ., 1976

[14] Dyer M., Frieze A., Kannan R., “A random polynomial algorithm for approximating the volume of convex bodies”, J. Assoc. Comput. Mach., 38:1 (1991), 1–17 | MR | Zbl

[15] Feige U., “A threshold of $\ln n$ for the approximating set cover”, Proc. of the 28th annual ACM symposium on theory of computing, ACM Press, New York, 1996, 314–318 | MR | Zbl

[16] Fernandez de la Vega W., “Max-cut has a randomized approximation scheme in dense graphs”, Random Structures and Algorithms, 8:3 (1989), 187–198 | 3.0.CO;2-U class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR

[17] Fernandez de la Vega W., Kenyon C., “A randomized approximation scheme for metric MAX-CUT”, Proc. of the 39th annual symposium on foundations of computer science, IEEE Comput. Soc. Press, Los Alamitos, CA, 1998, 468–471

[18] Freivalds R., “Probabilistic machines can use less running time”, Inform. Process. 77, Proc. of IFIP congr. 77, North-Holland, Amsterdam, 1977, 839–842 | MR

[19] Frieze A., Jerrum M., “Improved approximation algorithms for MAX $K$-CUT and MAX BISECTION”, Algorithmica, 18:1 (1997), 67–81 | DOI | MR | Zbl

[20] Goemans M. X., Williamson D. P., “New 3/4-approximation algorithms for the maximum satissiability problem”, SIAM J. Discrete Math., 7:4 (1994), 656–666 | DOI | MR | Zbl

[21] Goemans M. X., Williamson D. P., “$0{.}878$-approximation algorithms for MAX CUT and MAX-2SAT”, Proc. of the 26th annual ACM symposium on theory of computing, ACM Press, New York, 1994, 422–431 | MR

[22] Guha S., Khuller S., “Greedy strikes back: improved facility location algorithms”, J. Algorithms, 31:1 (1999), 228–248 | DOI | MR | Zbl

[23] Hassin R., Rubinstein S., “A $7/8$-approximation algorithm for metric MAX TSP”, Inform. Process. Lett., 81:5 (2002), 247–251 | DOI | MR | Zbl

[24] Hastad J., “Some optimal inapproximability results”, Proc. of the 28th ACM annual symposium on theory of computing, ACM Press, New York, 1997, 1–10 | MR

[25] Hohbaum D., “Heuristics for the fixed cost median problem”, Math. Programming, 22:1 (1982), 148–162 | DOI | MR

[26] Jain K., Mahdian M., Saberi A., “A new greedy approach for facility location problems”, Proc. of the 34th annual ACM symposium on theory of computing, ACM Press, New York, 2002, 731–740 | MR

[27] Johnson D. S., “Approximation algorithms for combinatorial problems”, J. Comput. System Sci., 9:3 (1974), 256–278 | MR | Zbl

[28] Karloff H., Zwick U., “A ($7/8-\varepsilon$)-approximation algorithm for MAX 3SAT”, Proc. of the 38th annual symposium on foundations of computer science, IEEE Comput. Soc. Press, Los Alamitos, CA, 1997, 406–415

[29] Karmarkar N., “A new polynomial-time algorithm for linear programming”, Combinatorica, 4:4 (1984), 373–395 | DOI | MR | Zbl

[30] Khachijan L. G., “Polynomial algorithm for linear programming”, DAN USSR, 244:5 (1979), 1093–1096, in Russian | MR

[31] Kohli R., Krishnamurti R., “Average performance of heuristics for satisfiability”, SIAM J. Discrete Math., 2:4 (1989), 508–523 | DOI | MR | Zbl

[32] Lieberherr K., Specker E., “Complexity of partial satisfaction”, J. Assoc. Comput. Mach., 28:2 (1981), 411–421 | MR | Zbl

[33] Motwani R., Raghavan P., Randomized algorithms, Cambridge Univ. Press, Cambridge, 1995 | MR | Zbl

[34] Papadimitriou C. H., “Euclidean traveling salesman problem is NP-complete”, Theoret. Comput. Sci., 4:3 (1977), 237–244 | DOI | MR | Zbl

[35] Papadimitriou C., Yannakakis M., “Optimization, approximation and complexity classes”, J. Comput. System Sci., 43:3 (1991), 425–440 | DOI | MR | Zbl

[36] Rabin M. O., “Probabilistic algorithm for testing primality”, J. Number Theory, 12:1 (1980), 128–138 | DOI | MR | Zbl

[37] Raghavan P., “Probabilistic construction of deterministic algorithms: approximating packing integer programs”, J. Comput. System Sci., 37:2 (1988), 130–143 | DOI | MR | Zbl

[38] Raghavan P., Tompson C. D., “Randomized rounding: a technique for provably good algorithms and algorithmic proofs”, Combinatorica, 37:4 (1987), 365–374 | DOI | MR

[39] Rajagopalan S., Vazirani V. V., “Primal-dual RNC approximation algorithms for (multi)-set (multi)-cover and covering integer programs”, Proc. of the annual symposium on foundations of computer science, IEEE Comput. Soc. Press, Los Alamitos, CA, 1993, 322–331 | MR

[40] Rao S., Smith W. D., “Improved approximation schemes for geometric graphs via “spanners” and “banyans””, Proc. of the 30th annual ACM symposium on theory of computing, ACM Press, New York, 1998, 540–550 | MR | Zbl

[41] Rödl V., “On a packing and covering problem”, European J. Combin., 6:1 (1985), 69–78 | MR | Zbl

[42] Rödl V., Thoma L., “Asymptotic packing and the random greedy algorithm”, Random Structures and Algorithms, 8:3 (1996), 161–177 | 3.0.CO;2-W class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[43] Shmoys D., Tardos E., Aardal K., “Approximation algorithms for facility location problems”, Proc. of the 29th annual ACM symposium on theory of computing, ACM Press, New York, 1997, 265–274

[44] Solovay R., Strassen V., “A fast Monte-Carlo test for primality”, SIAM J. Comput., 6:1 (1977), 84–85 | DOI | MR | Zbl

[45] Spencer J., Ten lectures on the probabilistic method, SIAM, Philadelphia, 1987 | MR

[46] Spencer J. H., “Asymptotic packing via a branching process”, Random Structures and Algorithms, 7:2 (1995), 167–172 | DOI | MR | Zbl

[47] Srinivasan A., “Improved approximations for packing and covering problems”, Proc. of the 27th annual ACM symposium on theory of computing, ACM Press, New York, 1995, 268–276 | Zbl

[48] Srivastav A., Stangier P., “Algorithmic Chernoff–Hoeffding inequalities in integer programming”, Random Structures and Algorithms, 8:1 (1996), 27–58 | 3.0.CO;2-T class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[49] Sviridenko M., “Best possible approximation algorithm for MAX SAT with cardinality constraint”, Algorithmica, 30:3 (2001), 398–405 | MR | Zbl

[50] Sviridenko M., “An improved approximation algorithm for the metric uncapacitated facility location problem”, Integer programming and combinatorial optimization, Proc. 9th International IPCO conference, Lecture Notes in Comput. Sci., 2337, Springer, Berlin, 2002, 240–257 | MR | Zbl

[51] Trevisan L., “When Hamming meets Euclid: the approximability of geometric TSP and MST”, Proc. of the 29th annual ACM symposium on theory of computing, ACM Press, New York, 1997, 21–29