License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2012.58
URN: urn:nbn:de:0030-drops-38488
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3848/
Go to the corresponding LIPIcs Volume Portal

Goyal, Navin ; Rademacher, Luis

Lower Bounds for the Average and Smoothed Number of Pareto Optima

pdf-format:
8.pdf (0.5 MB)

Abstract

Smoothed analysis of multiobjective 0-1 linear optimization has drawn considerable attention recently. In this literature, the number of Pareto-optimal solutions (i.e., solutions with the property that no other solution is at least as good in all the coordinates and better in at least one) for multiobjective optimization problems is the central object of study. In this paper, we prove several lower bounds for the expected number of Pareto optima. Our basic result is a lower bound of Omega_d(n^{d-1}) for optimization problems with d objectives and $n$ variables under fairly general conditions on the distributions of the linear objectives. Our proof relates the problem of lower bounding the number of Pareto optima to results in discrete geometry and geometric probability connected to arrangements of hyperplanes. We use our basic result to derive (1) To our knowledge, the first lower bound for natural multiobjective optimization problems. We illustrate this for the maximum spanning tree problem with randomly chosen edge weights. Our technique is sufficiently flexible to yield such lower bounds for other standard objective functions studied in this setting (such as multiobjective shortest path, TSP tour, matching). (2) Smoothed lower bound of min(Omega_d( n^{d-1.5} phi^{(d-\log d) (1-Theta(1/phi))}), 2^{Theta(n)}) for the 0-1 knapsack problem with d profits for phi-semirandom distributions for a version of the knapsack problem. This improves the recent lower bound of Brunsch and Röglin.

BibTeX - Entry

@InProceedings{goyal_et_al:LIPIcs:2012:3848,
  author =	{Navin Goyal and Luis Rademacher},
  title =	{{Lower Bounds for the Average and Smoothed Number of Pareto Optima}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
  pages =	{58--69},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2012/3848},
  URN =		{urn:nbn:de:0030-drops-38488},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.58},
  annote =	{Keywords: geometric probability, smoothed analysis, multiobjective optimization, Pareto optimal, knapsack}
}

Keywords: geometric probability, smoothed analysis, multiobjective optimization, Pareto optimal, knapsack
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Issue Date: 2012
Date of publication: 14.12.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI