Disser, Y. ; Skutella, M. (2015)
The Simplex Algorithm is NP-mighty.
26th ACM-SIAM Symposium on Discrete Algorithms. San Diego, USA (04.01.2015-06.01.2015)
doi: 10.1137/1.9781611973730.59
Konferenzveröffentlichung, Bibliographie
Kurzbeschreibung (Abstract)
We propose to classify the power of algorithms by the complexity of the problems that they can be used to solve. Instead of restricting to the problem a particular algorithm was designed to solve explicitly, however, we include problems that, with polynomial overhead, can be solved ‘implicitly’ during the algorithm's execution. For example, we allow to solve a decision problem by suitably transforming the input, executing the algorithm, and observing whether a specific bit in its internal configuration ever switches during the execution.
We show that the Simplex Method, the Network Simplex Method (both with Dantzig's original pivot rule), and the Successive Shortest Path Algorithm are NP-mighty, that is, each of these algorithms can be used to solve any problem in NP. This result casts a more favorable light on these algorithms' exponential worst-case running times. Furthermore, as a consequence of our approach, we obtain several novel hardness results. For example, for a given input to the Simplex Algorithm, deciding whether a given variable ever enters the basis during the algorithm's execution and determining the number of iterations needed are both NP-hard problems. Finally, we close a long-standing open problem in the area of network flows over time by showing that earliest arrival flows are NP-hard to obtain.
| Typ des Eintrags: | Konferenzveröffentlichung |
|---|---|
| Erschienen: | 2015 |
| Autor(en): | Disser, Y. ; Skutella, M. |
| Art des Eintrags: | Bibliographie |
| Titel: | The Simplex Algorithm is NP-mighty |
| Sprache: | Englisch |
| Publikationsjahr: | 2015 |
| Verlag: | SIAM |
| Buchtitel: | Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms |
| Veranstaltungstitel: | 26th ACM-SIAM Symposium on Discrete Algorithms |
| Veranstaltungsort: | San Diego, USA |
| Veranstaltungsdatum: | 04.01.2015-06.01.2015 |
| DOI: | 10.1137/1.9781611973730.59 |
| Kurzbeschreibung (Abstract): | We propose to classify the power of algorithms by the complexity of the problems that they can be used to solve. Instead of restricting to the problem a particular algorithm was designed to solve explicitly, however, we include problems that, with polynomial overhead, can be solved ‘implicitly’ during the algorithm's execution. For example, we allow to solve a decision problem by suitably transforming the input, executing the algorithm, and observing whether a specific bit in its internal configuration ever switches during the execution. We show that the Simplex Method, the Network Simplex Method (both with Dantzig's original pivot rule), and the Successive Shortest Path Algorithm are NP-mighty, that is, each of these algorithms can be used to solve any problem in NP. This result casts a more favorable light on these algorithms' exponential worst-case running times. Furthermore, as a consequence of our approach, we obtain several novel hardness results. For example, for a given input to the Simplex Algorithm, deciding whether a given variable ever enters the basis during the algorithm's execution and determining the number of iterations needed are both NP-hard problems. Finally, we close a long-standing open problem in the area of network flows over time by showing that earliest arrival flows are NP-hard to obtain. |
| Fachbereich(e)/-gebiet(e): | Exzellenzinitiative Exzellenzinitiative > Graduiertenschulen Exzellenzinitiative > Graduiertenschulen > Graduate School of Computational Engineering (CE) 04 Fachbereich Mathematik 04 Fachbereich Mathematik > Optimierung 04 Fachbereich Mathematik > Optimierung > Discrete Optimization |
| Hinterlegungsdatum: | 14 Okt 2016 07:27 |
| Letzte Änderung: | 18 Aug 2022 12:10 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum