Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  Typical Properties of Winners and Losers in Discrete Optimization

Beier, R., & Vöcking, B. (2004). Typical Properties of Winners and Losers in Discrete Optimization. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC-04) (pp. 343-352). New York, USA: ACM.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Beier, Rene1, Autor           
Vöcking, Berthold1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2005-05-232004
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: New York, USA : ACM
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 232040
Anderer: Local-ID: C1256428004B93B8-BBA1FFF86747F055C1256EB6004F655D-Beier2004c
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Chicago, USA
Start-/Enddatum: 2004-06-13

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC-04)
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: New York, USA : ACM
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 343 - 352 Identifikator: ISBN: 1-58113-852-0