Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2020) | last year (2019) | two years ago (2018) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Beier, Rene Vöcking, Berthold dblp dblp Not MPG Author(s): Berthold Vöcking
 Editor(s):
 BibTeX cite key*: Beier2004c

 Title, Booktitle
 Title*: Typical Properties of Winners and Losers in Discrete Optimization Booktitle*: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC-04)

 Event, URLs
 URL of the conference: http://people.cs.uchicago.edu/~stoc04/ URL for downloading the paper: http://www.mpi-sb.mpg.de/~rbeier/winner.ps.gz Event Address*: Chicago, USA Language: English Event Date* (no longer used): Organization: Association of Computing Machinery (ACM) Event Start Date: 13 June 2004 Event End Date: 15 June 2004

 Publisher
 Name*: ACM URL: http://www.acm.org Address*: New York, USA Type:

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: June Pages: 343-352 Year*: 2004 VG Wort Pages: 40 ISBN/ISSN: 1-58113-852-0 Sequence Number: DOI:

 (LaTeX) Abstract: We present a probabilistic analysis for a large class of combinatorial optimization problems containing, e.g., all {\em binary optimization problems} defined by linear constraints and a linear objective function over $\{0,1\}^n$. By parameterizing which constraints are of stochastic and which are of adversarial nature, we obtain a semi-random input model that enables us to do a general average-case analysis for a large class of optimization problems while at the same time taking care for the combinatorial structure of individual problems. Our analysis covers various probability distributions for the choice of the stochastic numbers and includes {\em smoothed analysis} with Gaussian and other kinds of perturbation models as a special case. In fact, we can exactly characterize the smoothed complexity of optimization problems in terms of their random worst-case complexity. \begin{center} \begin{minipage}{0.42\textwidth} A binary optimization problem has a {\em polynomial smoothed complexity} if and only if it has a pseudopolynomial complexity. \end{minipage} \end{center} Our analysis is centered around structural properties of binary optimization problems, called {\em winner}, {\em loser}, and {\em feasibility gaps}. We show, when the coefficients of the objective function and/or some of the constraints are stochastic, then there usually exist a polynomial $n^{-\Omega(1)}$ gap between the best and the second best solution as well as a polynomial slack to the boundary of the constraints. Similar to the condition number for linear programming, these gaps describe the sensitivity of the optimal solution to slight perturbations of the input and can be used to bound the necessary accuracy as well as the complexity for solving an instance. We exploit the gaps in form of an adaptive rounding scheme increasing the accuracy of calculation until the optimal solution is found. The strength of our techniques is illustrated by applications to various \npc-hard optimization problems from mathematical programming, network design, and scheduling for which we obtain the the first algorithms with polynomial average-case/smoothed complexity. Keywords: optimization problems, average-case analysis, smoothed analysis} Download Access Level: MPG

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{Beier2004c,
AUTHOR = {Beier, Rene and V{\"o}cking, Berthold},
TITLE = {Typical Properties of Winners and Losers in Discrete Optimization},
BOOKTITLE = {Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC-04)},
PUBLISHER = {ACM},
YEAR = {2004},
ORGANIZATION = {Association of Computing Machinery (ACM)},
PAGES = {343--352},