3 Search Results for "Timmermans, Veerle"

Document
DOI: 10.4230/LIPIcs.MFCS.2025.52
On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy

Authors: Christoph Grüne and Lasse Wulf

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Recoverable robust optimization is a popular multi-stage approach, in which it is possible to adjust a first-stage solution after the uncertain cost scenario is revealed. We consider recoverable robust optimization in combination with discrete budgeted uncertainty. In this setting, it seems plausible that many problems become Σ^p₃-complete and therefore it is impossible to find compact IP formulations of them (unless the unlikely conjecture NP = Σ^p₃ holds). Even though this seems plausible, few concrete results of this kind are known. In this paper, we fill that gap of knowledge. We consider recoverable robust optimization for the nominal problems of Sat, 3Sat, vertex cover, dominating set, set cover, hitting set, feedback vertex set, feedback arc set, uncapacitated facility location, p-center, p-median, independent set, clique, subset sum, knapsack, partition, scheduling, Hamiltonian path/cycle (directed/undirected), TSP, k-directed disjoint path (k ≥ 2), and Steiner tree. We show that for each of these problems, and for each of three widely used distance measures, the recoverable robust problem becomes Σ^p₃-complete. Concretely, we show that all these problems share a certain abstract property and prove that this property implies that their robust recoverable counterpart is Σ^p₃-complete. This reveals the insight that all the above problems are Σ^p₃-complete "for the same reason". Our result extends a recent framework by Grüne and Wulf.
Cite as

Christoph Grüne and Lasse Wulf. On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 52:1-52:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grune_et_al:LIPIcs.MFCS.2025.52,
  author =	{Gr\"{u}ne, Christoph and Wulf, Lasse},
  title =	{{On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{52:1--52:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.52},
  URN =		{urn:nbn:de:0030-drops-241596},
  doi =		{10.4230/LIPIcs.MFCS.2025.52},
  annote =	{Keywords: Complexity, Robust Optimization, Recoverable Robust Optimization, Two-Stage Problems, Polynomial Hierarchy, Sigma 2, Sigma 3}
}
Document
DOI: 10.4230/LIPIcs.SAND.2022.4
Atomic Splittable Flow Over Time Games

Authors: Antonia Adamik and Leon Sering

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
In an atomic splittable flow over time game, finitely many players route flow dynamically through a network, in which edges are equipped with transit times, specifying the traversing time, and with capacities, restricting flow rates. Infinitesimally small flow particles controlled by the same player arrive at a constant rate at the player’s origin and the player’s goal is to maximize the flow volume that arrives at the player’s destination within a given time horizon. Here, the flow dynamics are described by the deterministic queuing model, i.e., flow of different players merges perfectly, but excessive flow has to wait in a queue in front of the bottle-neck. In order to determine Nash equilibria in such games, the main challenge is to consider suitable definitions for the players' strategies, which depend on the level of information the players receive throughout the game. For the most restricted version, in which the players receive no information on the network state at all, we can show that there is no Nash equilibrium in general, not even for networks with only two edges. However, if the current edge congestions are provided over time, the players can adapt their route choices dynamically. We show that a profile of those strategies always lead to a unique feasible flow over time. Hence, those atomic splittable flow over time games are well-defined. For parallel-edge networks Nash equilibria exists and the total flow arriving in time equals the value of a maximum flow over time leading to a price of anarchy of 1.
Cite as

Antonia Adamik and Leon Sering. Atomic Splittable Flow Over Time Games. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{adamik_et_al:LIPIcs.SAND.2022.4,
  author =	{Adamik, Antonia and Sering, Leon},
  title =	{{Atomic Splittable Flow Over Time Games}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.4},
  URN =		{urn:nbn:de:0030-drops-159462},
  doi =		{10.4230/LIPIcs.SAND.2022.4},
  annote =	{Keywords: Flows Over Time, Deterministic Queuing, Atomic Splittable Games, Equilibria, Traffic, Cooperation}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2018.13
Oligopolistic Competitive Packet Routing

Authors: Britta Peis, Bjoern Tauer, Veerle Timmermans, and Laura Vargas Koch

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Abstract
Oligopolistic competitive packet routing games model situations in which traffic is routed in discrete units through a network over time. We study a game-theoretic variant of packet routing, where in contrast to classical packet routing, we are lacking a central authority to decide on an oblivious routing protocol. Instead, selfish acting decision makers ("players") control a certain amount of traffic each, which needs to be sent as fast as possible from a player-specific origin to a player-specific destination through a commonly used network. The network is represented by a directed graph, each edge of which being endowed with a transit time, as well as a capacity bounding the number of traffic units entering an edge simultaneously. Additionally, a priority policy on the set of players is publicly known with respect to which conflicts at intersections are resolved. We prove the existence of a pure Nash equilibrium and show that it can be constructed by sequentially computing an integral earliest arrival flow for each player. Moreover, we derive several tight bounds on the price of anarchy and the price of stability in single source games.
Cite as

Britta Peis, Bjoern Tauer, Veerle Timmermans, and Laura Vargas Koch. Oligopolistic Competitive Packet Routing. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 13:1-13:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{peis_et_al:OASIcs.ATMOS.2018.13,
  author =	{Peis, Britta and Tauer, Bjoern and Timmermans, Veerle and Vargas Koch, Laura},
  title =	{{Oligopolistic Competitive Packet Routing}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{13:1--13:22},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.13},
  URN =		{urn:nbn:de:0030-drops-97186},
  doi =		{10.4230/OASIcs.ATMOS.2018.13},
  annote =	{Keywords: Competitive Packet Routing, Nash Equilibrium, Oligopoly, Efficiency of Equilibria, Priority Policy}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2022
  • 1 2018

  • Refine by Author
  • 1 Adamik, Antonia
  • 1 Grüne, Christoph
  • 1 Peis, Britta
  • 1 Sering, Leon
  • 1 Tauer, Bjoern
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 1 Mathematics of computing → Network flows
  • 1 Networks → Network algorithms
  • 1 Theory of computation → Network flows
  • 1 Theory of computation → Network games
  • 1 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 1 Atomic Splittable Games
  • 1 Competitive Packet Routing
  • 1 Complexity
  • 1 Cooperation
  • 1 Deterministic Queuing
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact