Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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:




Note, Abstract, ©


(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},
ADDRESS = {Chicago, USA},
MONTH = {June},
ISBN = {1-58113-852-0},
}


Entry last modified by Christine Kiesel, 05/23/2005
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Rene Beier
Created
06/17/2004 04:27:12 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Sabine Krott
Sabine Krott
Rene Beier
Rene Beier
Edit Dates
23.05.2005 15:00:31
02.02.2005 12:06:56
02.02.2005 10:35:09
06/17/2004 04:28:56 PM
06/17/2004 04:27:12 PM