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.