Lower Bounds for the Average and Smoothed Number of Pareto-Optima
by Tobias Brunsch, Navin Goyal, Luis Rademacher, and Heiko Röglin
Theory of Computing, Volume 10(10), pp. 237-256, 2014
Bibliography with links to cited articles
[1] René Beier, Heiko Röglin, and Berthold Vöcking: The smoothed number of Pareto optimal solutions in bicriteria integer optimization. In Proc. 12th Ann. Conf. on Integer Programming and Combinatorial Optimization (IPCO’07), pp. 53–67. Springer, 2007. [doi:10.1007/978-3-540-72792-7_5]
[2] René Beier and Berthold Vöcking: Random knapsack in expected polynomial time. J. Comput. Syst. Sci., 69(3):306–329, 2004. Preliminary version in STOC’03. [doi:10.1016/j.jcss.2004.04.004]
[3] René Beier and Berthold Vöcking: Typical properties of winners and losers in discrete optimization. SIAM J. Comput., 35(4):855–881, 2006. Preliminary version in STOC’04. [doi:10.1137/S0097539705447268]
[4] Jon Louis Bentley, Hsiang-Tsung Kung, Mario Schkolnick, and Clark D. Thompson: On the average number of maxima in a set of vectors and applications. J. ACM, 25(4):536–543, 1978. [doi:10.1145/322092.322095]
[5] Béla Bollobás: Combinatorics: Set systems, hypergraphs, families of vectors and combinatorial probability. Cambridge University Press, Cambridge, 1986.
[6] Tobias Brunsch and Heiko Röglin: Lower bounds for the smoothed number of Pareto optimal solutions. In Theory and Applications of Models of Computation - 8th Annual Conference (TAMC’11), LNCS 6648, pp. 416–427. Springer, 2011. [doi:10.1007/978-3-642-20877-5_41, arXiv:abs/1012.1163]
[7] Tobias Brunsch and Heiko Röglin: Improved smoothed analysis of multiobjective optimization. In Proc. 44th STOC, pp. 407–426. ACM Press, 2012. [doi:10.1145/2213977.2214016, arXiv:abs/1111.1546]
[8] Christian Buchta: On the average number of maxima in a set of vectors. Inf. Process. Lett., 33(2):63–65, 1989. [doi:10.1016/0020-0190(89)90156-7]
[9] Luc Devroye: A note on finding convex hulls via maximal vectors. Inf. Process. Lett., 11(1):53–56, 1980. [doi:10.1016/0020-0190(80)90036-8]
[10] David L. Donoho and Jared Tanner: Counting the faces of randomly-projected hypercubes and orthants, with applications. Discrete Comput. Geom., 43(3):522–541, 2010. [doi:10.1007/s00454-009-9221-z, arXiv:0807.3590]
[11] Matthias Ehrgott: Multicriteria Optimization (2nd ed.). Springer, 2005. [doi:10.1007/3-540-27659-9]
[12] Jacob E. Goodman and Joseph O’Rourke: Handbook of Discrete and Computational Geometry. Discrete Mathematics and its Applications. Chapman & Hall/CRC, 2004.
[13] Navin Goyal and Luis Rademacher: Lower bounds for the average and smoothed number of Pareto optima. In IARCS Annual Conf. on Foundations of Software Technology and Theoretical Computer Science (FSTTCS’12), pp. 58–69. Springer, 2012. [doi:10.4230/LIPIcs.FSTTCS.2012.58, arXiv:abs/1107.3876]
[14] Fabrizio Grandoni, Ramamoorthi Ravi, and Mohit Singh: Iterative rounding for multi-objective optimization problems. In Proc. 17th Ann. European Symp. on Algorithms (ESA’09), pp. 95–106, 2009. [doi:10.1007/978-3-642-04128-0_9]
[15] Ankur Moitra and Ryan O’Donnell: Pareto optimal solutions for smoothed analysts. SIAM J. Comput., 41(5):1266–1284, 2012. Preliminary version in STOC’11. [doi:10.1137/110851833]
[16] Matthias Müller-Hannemann and Karsten Weihe: Pareto shortest paths is often feasible in practice. In Algorithm Engineering, 5th Internat. Workshop (WAE’01), pp. 185–197. Springer, 2001. [doi:10.1007/3-540-44688-5_15]
[17] George L. Nemhauser and Zev Ullmann: Discrete dynamic programming and capital allocation. Management Science, 15(9):494–505, 1969. [doi:10.1287/mnsc.15.9.494]
[18] Franco P. Preparata and Michael Ian Shamos: Computational Geometry: An Introduction. Texts and Monographs in Computer Science. Springer, New York, 1985. [doi:10.1007/978-1-4612-1098-6]
[19] Heiko Röglin and Shang-Hua Teng: Smoothed analysis of multiobjective optimization. In Proc. 50th FOCS, pp. 681–690. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.21]
[20] Rolf Schneider: Recent results on random polytopes: A survey. Bollettino dell’Unione Matematica Italiana, Ser. (9), 1:17–40, 2008.
[21] Rolf Schneider and Wolfgang Weil: Stochastic and integral geometry. Probability and its Applications (New York). Springer, Berlin, 2008. [doi:10.1007/978-3-540-78859-1]
[22] Daniel A. Spielman and Shang-Hua Teng: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):385–463, 2004. Preliminary version in STOC’01. [doi:10.1145/990308.990310]
[23] J.G. Wendel: A problem in geometric probability. Mathematica Scandinavica, 11:109–112, 1962. Found at Mathematica Scandinavica.