10 Search Results for "Gairing, Martin"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.9
Optimal Competitive Ratio for Optimization Problems with Congestion Effects

Authors: Miriam Fischer, Dario Paccagnan, and Cosimo Vinci

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
In this work we study online optimization problems with congestion effects. These are problems where tasks arrive online and a decision maker is required to allocate them on the fly to available resources in order to minimize the cost suffered, which grows with the amount of resources used. This class of problems corresponds to the online counterpart of well-known studied problems, including optimization problems with diseconomies of scale [Konstantin Makarychev and Maxim Sviridenko, 2018], minimum cost in congestion games [Gairing and Paccagnan, 2023], and load balancing problems [Baruch Awerbuch et al., 1995]. Within this setting, our work settles the problem of designing online algorithms with optimal competitive ratio, i.e., algorithms whose incurred cost is as close as possible to that of an oracle with complete knowledge of the future instance ahead of time. We provide three contributions underpinning this result. First, we show that no online algorithm can achieve a competitive ratio below a given factor depending solely on the resource costs. Second, we show that, when guided by carefully modified cost functions, the greedy algorithm achieves a competitive ratio matching this lower bound and thus is optimal. Finally, we show how to compute such modified cost functions in polynomial time.
Cite as

Miriam Fischer, Dario Paccagnan, and Cosimo Vinci. Optimal Competitive Ratio for Optimization Problems with Congestion Effects. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 9:1-9:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.APPROX/RANDOM.2025.9,
  author =	{Fischer, Miriam and Paccagnan, Dario and Vinci, Cosimo},
  title =	{{Optimal Competitive Ratio for Optimization Problems with Congestion Effects}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{9:1--9:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.9},
  URN =		{urn:nbn:de:0030-drops-243754},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.9},
  annote =	{Keywords: Online Algorithms, Competitive Ratio, Algorithmic Game Theory, Greedy Algorithms, Congestion Games}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.95
ARRIVAL: Recursive Framework & 𝓁₁-Contraction

Authors: Sebastian Haslebacher

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
ARRIVAL is the problem of deciding which out of two possible destinations will be reached first by a token that moves deterministically along the edges of a directed graph, according to so-called switching rules. It is known to lie in NP ∩ CoNP, but not known to lie in 𝖯. The state-of-the-art algorithm due to Gärtner et al. (ICALP `21) runs in time 2^{𝒪(√n log n)} on an n-vertex graph. We prove that ARRIVAL can be solved in time 2^{𝒪(k log² n)} on n-vertex graphs of treewidth k. Our algorithm is derived by adapting a simple recursive algorithm for a generalization of ARRIVAL called G-ARRIVAL. This simple recursive algorithm acts as a framework from which we can also rederive the subexponential upper bound of Gärtner et al. Our second result is a reduction from G-ARRIVAL to the problem of finding an approximate fixed point of an 𝓁₁-contracting function f : [0, 1]ⁿ → [0, 1]ⁿ. Finding such fixed points is a well-studied problem in the case of the 𝓁₂-metric and the 𝓁_∞-metric, but little is known about the 𝓁₁-case. Both of our results highlight parallels between ARRIVAL and the Simple Stochastic Games (SSG) problem. Concretely, Chatterjee et al. (SODA `23) gave an algorithm for SSG parameterized by treewidth that achieves a similar bound as we do for ARRIVAL, and SSG is known to reduce to 𝓁_∞-contraction.
Cite as

Sebastian Haslebacher. ARRIVAL: Recursive Framework & 𝓁₁-Contraction. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 95:1-95:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{haslebacher:LIPIcs.ICALP.2025.95,
  author =	{Haslebacher, Sebastian},
  title =	{{ARRIVAL: Recursive Framework \& 𝓁₁-Contraction}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{95:1--95:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.95},
  URN =		{urn:nbn:de:0030-drops-234723},
  doi =		{10.4230/LIPIcs.ICALP.2025.95},
  annote =	{Keywords: ARRIVAL, G-ARRIVAL, Deterministic Random Walk, Rotor-Routing, 𝓁₁-Contraction, Banach Fixed Point}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.39
A Quasi-Polynomial Time Algorithm for Multi-Arrival on Tree-Like Multigraphs

Authors: Ebrahim Ghorbani, Jonah Leander Hoff, and Matthias Mnich

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Propp machines, or rotor-router models, are a classic tool to simulate random systems in forms of Markov chains by deterministic systems. To this end, the nodes of the Markov chain are replaced by switching nodes, which maintain a queue over their outgoing arcs, and a particle sent through the system traverses the top arc of the queue which is then moved to the end of the queue and the particle arrives at the next node. A key question to answer about such systems is whether a single particle can reach a particular target node, given as input an initial configuration of the queues at all switching nodes. This question was introduced by Dohrau et al. (2017) under the name of Arrival. A major open question is whether Arrival can be solved in polynomial time, as it is known to lie in NP ∩ co-NP; yet the fastest known algorithm for general instances takes subexponential time (Gärtner et al., ICALP 2021). We consider a generalized version of Arrival introduced by Auger et al. (RP 2023), which requires routing multiple (potentially exponentially many) particles through a rotor graph. The Multi-Arrival problem is to determine the particle configuration that results from moving all particles from a given initial configuration to sinks. Auger et al. showed that for path-like rotor graphs with a certain uniform rotor order, the problem can be solved in polynomial time. Our main result is a quasi-polynomial-time algorithm for Multi-Arrival on tree-like rotor graphs for arbitrary rotor orders. Tree-like rotor graphs are directed multigraphs which can be obtained from undirected trees by replacing each edge by an arbitrary number of arcs in either or both directions. For trees of bounded contracted height, such as paths, the algorithm runs in polynomial time and thereby generalizes the result by Auger et al.. Moreover, we give a polynomial-time algorithm for Multi-Arrival on tree-like rotor graphs without parallel arcs.
Cite as

Ebrahim Ghorbani, Jonah Leander Hoff, and Matthias Mnich. A Quasi-Polynomial Time Algorithm for Multi-Arrival on Tree-Like Multigraphs. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ghorbani_et_al:LIPIcs.STACS.2025.39,
  author =	{Ghorbani, Ebrahim and Leander Hoff, Jonah and Mnich, Matthias},
  title =	{{A Quasi-Polynomial Time Algorithm for Multi-Arrival on Tree-Like Multigraphs}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{39:1--39:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.39},
  URN =		{urn:nbn:de:0030-drops-228658},
  doi =		{10.4230/LIPIcs.STACS.2025.39},
  annote =	{Keywords: Arrival, Rotor-routing, Tree-like Multigraph, Path-Like Multigraph, Fixed-Parameter Tractability}
}
Document
DOI: 10.4230/DagRep.12.5.92
Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 22192)

Authors: Martin Gairing, Carolina Osorio, Britta Peis, David Watling, and Katharina Eickhoff

Published in: Dagstuhl Reports, Volume 12, Issue 5 (2022)

Abstract
Traffic assignment models are crucial for transport planners to be able to predict the congestion, environmental and social impacts of transport policies, for example in the light of possible changes to the infrastructure, to the transport services offered, or to the prices charged to travellers. The motivation for this series of seminars - of which this seminar was the third - is the prevalence in the transportation community of basing such predictions on complex computer-based simulations that are capable of resolving many elements of a real systems, while on the other hand, the theory of dynamic traffic assignments (in terms of equilibrium existence, computability and efficiency) had not matured to the point matching the model complexity inherent in simulations. Progress has been made on this issue in the first two seminars (Dagstuhl Seminar 15412 and 18102), by bringing together leading scientists in the areas of traffic simulation, algorithmic game theory and dynamic traffic assignment. We continued this process this seminar. Moreover, we started to address the growing real-life challenge of new kinds of 'mobility service' emerging, before the tools are available to incorporate them in such planning models. These services include intelligent/dynamic ride-sharing and car-sharing, through to fully autonomous vehicles, provided potentially by a variety of competing operators.
Cite as

Martin Gairing, Carolina Osorio, Britta Peis, David Watling, and Katharina Eickhoff. Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 22192). In Dagstuhl Reports, Volume 12, Issue 5, pp. 92-111, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{gairing_et_al:DagRep.12.5.92,
  author =	{Gairing, Martin and Osorio, Carolina and Peis, Britta and Watling, David and Eickhoff, Katharina},
  title =	{{Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 22192)}},
  pages =	{92--111},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{5},
  editor =	{Gairing, Martin and Osorio, Carolina and Peis, Britta and Watling, David and Eickhoff, Katharina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.5.92},
  URN =		{urn:nbn:de:0030-drops-174441},
  doi =		{10.4230/DagRep.12.5.92},
  annote =	{Keywords: Algorithms and Complexity of traffic equilibrium computations, Dynamic traffic assignment models, Simulation and network optimization}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.32
Existence and Complexity of Approximate Equilibria in Weighted Congestion Games

Authors: George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, Diogo Poças, and Clara Waldmann

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We study the existence of approximate pure Nash equilibria (α-PNE) in weighted atomic congestion games with polynomial cost functions of maximum degree d. Previously it was known that d-approximate equilibria always exist, while nonexistence was established only for small constants, namely for 1.153-PNE. We improve significantly upon this gap, proving that such games in general do not have Θ̃(√d)-approximate PNE, which provides the first super-constant lower bound. Furthermore, we provide a black-box gap-introducing method of combining such nonexistence results with a specific circuit gadget, in order to derive NP-completeness of the decision version of the problem. In particular, deploying this technique we are able to show that deciding whether a weighted congestion game has an Õ(√d)-PNE is NP-complete. Previous hardness results were known only for the special case of exact equilibria and arbitrary cost functions. The circuit gadget is of independent interest and it allows us to also prove hardness for a variety of problems related to the complexity of PNE in congestion games. For example, we demonstrate that the question of existence of α-PNE in which a certain set of players plays a specific strategy profile is NP-hard for any α < 3^(d/2), even for unweighted congestion games. Finally, we study the existence of approximate equilibria in weighted congestion games with general (nondecreasing) costs, as a function of the number of players n. We show that n-PNE always exist, matched by an almost tight nonexistence bound of Θ̃(n) which we can again transform into an NP-completeness proof for the decision problem.
Cite as

George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, Diogo Poças, and Clara Waldmann. Existence and Complexity of Approximate Equilibria in Weighted Congestion Games. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{christodoulou_et_al:LIPIcs.ICALP.2020.32,
  author =	{Christodoulou, George and Gairing, Martin and Giannakopoulos, Yiannis and Po\c{c}as, Diogo and Waldmann, Clara},
  title =	{{Existence and Complexity of Approximate Equilibria in Weighted Congestion Games}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{32:1--32:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.32},
  URN =		{urn:nbn:de:0030-drops-124392},
  doi =		{10.4230/LIPIcs.ICALP.2020.32},
  annote =	{Keywords: Atomic congestion games, existence of equilibria, pure Nash equilibria, approximate equilibria, hardness of equilibria}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.124
Reachability Switching Games

Authors: John Fearnley, Martin Gairing, Matthias Mnich, and Rahul Savani

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
In this paper, we study the problem of deciding the winner of reachability switching games. We study zero-, one-, and two-player variants of these games. We show that the zero-player case is NL-hard, the one-player case is NP-complete, and that the two-player case is PSPACE-hard and in EXPTIME. For the zero-player case, we also show P-hardness for a succinctly-represented model that maintains the upper bound of NP n coNP. For the one- and two-player cases, our results hold in both the natural, explicit model and succinctly-represented model. We also study the structure of winning strategies in these games, and in particular we show that exponential memory is required in both the one- and two-player settings.
Cite as

John Fearnley, Martin Gairing, Matthias Mnich, and Rahul Savani. Reachability Switching Games. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 124:1-124:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fearnley_et_al:LIPIcs.ICALP.2018.124,
  author =	{Fearnley, John and Gairing, Martin and Mnich, Matthias and Savani, Rahul},
  title =	{{Reachability Switching Games}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{124:1--124:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.124},
  URN =		{urn:nbn:de:0030-drops-91282},
  doi =		{10.4230/LIPIcs.ICALP.2018.124},
  annote =	{Keywords: Deterministic Random Walks, Model Checking, Reachability, Simple Stochastic Game, Switching Systems}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.150
The Price of Stability of Weighted Congestion Games

Authors: George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, and Paul G. Spirakis

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We give exponential lower bounds on the Price of Stability (PoS) of weighted congestion games with polynomial cost functions. In particular, for any positive integer d we construct rather simple games with cost functions of degree at most d which have a PoS of at least Omega(Phi_d)^{d+1}, where Phi_d ~ d/ln d is the unique positive root of equation x^{d+1}=(x+1)^d. This essentially closes the huge gap between Theta(d) and Phi_d^{d+1} and asymptotically matches the Price of Anarchy upper bound. We further show that the PoS remains exponential even for singleton games. More generally, we also provide a lower bound of Omega((1+1/alpha)^d/d) on the PoS of alpha-approximate Nash equilibria, even for singleton games. All our lower bounds extend to network congestion games, and hold for mixed and correlated equilibria as well. On the positive side, we give a general upper bound on the PoS of alpha-approximate Nash equilibria, which is sensitive to the range W of the player weights and the approximation parameter alpha. We do this by explicitly constructing a novel approximate potential function, based on Faulhaber's formula, that generalizes Rosenthal's potential in a continuous, analytic way. From the general theorem, we deduce two interesting corollaries. First, we derive the existence of an approximate pure Nash equilibrium with PoS at most (d+3)/2; the equilibrium's approximation parameter ranges from Theta(1) to d+1 in a smooth way with respect to W. Secondly, we show that for unweighted congestion games, the PoS of alpha-approximate Nash equilibria is at most (d+1)/alpha.
Cite as

George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, and Paul G. Spirakis. The Price of Stability of Weighted Congestion Games. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 150:1-150:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{christodoulou_et_al:LIPIcs.ICALP.2018.150,
  author =	{Christodoulou, George and Gairing, Martin and Giannakopoulos, Yiannis and Spirakis, Paul G.},
  title =	{{The Price of Stability of Weighted Congestion Games}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{150:1--150:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.150},
  URN =		{urn:nbn:de:0030-drops-91541},
  doi =		{10.4230/LIPIcs.ICALP.2018.150},
  annote =	{Keywords: Congestion games, price of stability, Nash equilibrium, approximate equilibrium, potential games}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.30
Strategic Contention Resolution with Limited Feedback

Authors: George Christodoulou, Martin Gairing, Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul Spirakis

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
In this paper, we study contention resolution protocols from a game-theoretic perspective. We focus on acknowledgment-based protocols, where a user gets feedback from the channel only when she attempts transmission. In this case she will learn whether her transmission was successful or not. Users that do not transmit will not receive any feedback. We are interested in equilibrium protocols, where no player has an incentive to deviate. The limited feedback makes the design of equilibrium protocols a hard task as best response policies usually have to be modeled as Partially Observable Markov Decision Processes, which are hard to analyze. Nevertheless, we show how to circumvent this for the case of two players and present an equilibrium protocol. For many players, we give impossibility results for a large class of acknowledgment-based protocols, namely age-based and backoff protocols with finite expected finishing time. Finally, we provide an age-based equilibrium protocol, which has infinite expected finishing time, but every player finishes in linear time with high probability.
Cite as

George Christodoulou, Martin Gairing, Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul Spirakis. Strategic Contention Resolution with Limited Feedback. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{christodoulou_et_al:LIPIcs.ESA.2016.30,
  author =	{Christodoulou, George and Gairing, Martin and Nikoletseas, Sotiris and Raptopoulos, Christoforos and Spirakis, Paul},
  title =	{{Strategic Contention Resolution with Limited Feedback}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{30:1--30:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.30},
  URN =		{urn:nbn:de:0030-drops-63813},
  doi =		{10.4230/LIPIcs.ESA.2016.30},
  annote =	{Keywords: contention resolution, acknowledgment-based protocols, game theory}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.226
Complexity and Approximation of the Continuous Network Design Problem

Authors: Martin Gairing, Tobias Harks, and Max Klimm

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
We revisit a classical problem in transportation, known as the continuous (bilevel) network design problem, CNDP for short. Given a graph for which the latency of each edge depends on the ratio of the edge flow and the capacity installed, the goal is to find an optimal investment in edge capacities so as to minimize the sum of the routing cost of the induced Wardrop equilibrium and the investment cost for installing the capacity. While this problem is considered as challenging in the literature, its complexity status was still unknown. We close this gap showing that CNDP is strongly NP-complete and APX-hard, both on directed and undirected networks and even for instances with affine latencies. As for the approximation of the problem, we first provide a detailed analysis for a heuristic studied by Marcotte for the special case of monomial latency functions (Math. Program., Vol. 34, 1986). We derive a closed form expression of its approximation guarantee for arbitrary sets of latency functions. We then propose a different approximation algorithm and show that it has the same approximation guarantee. However, we show that using the better of the two approximation algorithms results in a strictly improved approximation guarantee for which we derive a closed form expression. For affine latencies, e.g., this algorithm achieves a 49/41-approximation which improves on the 5/4 that has been shown before by Marcotte. We finally discuss the case of hard budget constraints on the capacity investment.
Cite as

Martin Gairing, Tobias Harks, and Max Klimm. Complexity and Approximation of the Continuous Network Design Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 226-241, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{gairing_et_al:LIPIcs.APPROX-RANDOM.2014.226,
  author =	{Gairing, Martin and Harks, Tobias and Klimm, Max},
  title =	{{Complexity and Approximation of the Continuous Network Design Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{226--241},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.226},
  URN =		{urn:nbn:de:0030-drops-46998},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.226},
  annote =	{Keywords: Bilevel optimization, Optimization under equilibrium constraints, Network design, Wardrop equilibrium, Computational complexity, Approximation algorit}
}
Document
DOI: 10.4230/DagSemProc.05011.19
The Price of Anarchy for Polynomial Social Cost

Authors: Martin Gairing, Thomas Lücking, Marios Mavronicolas, and Burkhard Monien

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

Abstract
In this work, we consider an interesting variant of the well-studied KP model [KP99] for selfish routing that reflects some influence from the much older Wardrop [War52]. In the new model, user traffics are still unsplittable, while social cost is now the expectation of the sum, over all links, of a certain polynomial evaluated at the total latency incurred by all users choosing the link; we call it polynomial social cost. The polynomials that we consider have non-negative coefficients. We are interested in evaluating Nash equilibria in this model, and we use the Price of Anarchy as our evaluation measure. We prove the Fully Mixed Nash Equilibrium Conjecture for identical users and two links, and establish an approximate version of the conjecture for arbitrary many links. Moreover, we give upper bounds on the Price of Anarchy.
Cite as

Martin Gairing, Thomas Lücking, Marios Mavronicolas, and Burkhard Monien. The Price of Anarchy for Polynomial Social Cost. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{gairing_et_al:DagSemProc.05011.19,
  author =	{Gairing, Martin and L\"{u}cking, Thomas and Mavronicolas, Marios and Monien, Burkhard},
  title =	{{The Price of Anarchy for Polynomial Social Cost}},
  booktitle =	{Computing and Markets},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.19},
  URN =		{urn:nbn:de:0030-drops-2005},
  doi =		{10.4230/DagSemProc.05011.19},
  annote =	{Keywords: selfish routing , KP-model , price of anarchy , fully mixed Nash Equilibrium}
}
  • Refine by Type
  • 10 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2022
  • 1 2020
  • 2 2018
  • 1 2016
  • Show More...

  • Refine by Author
  • 7 Gairing, Martin
  • 3 Christodoulou, George
  • 2 Giannakopoulos, Yiannis
  • 2 Mnich, Matthias
  • 1 Eickhoff, Katharina
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs
  • 1 DagRep
  • 1 DagSemProc

  • Refine by Classification
  • 3 Theory of computation → Algorithmic game theory
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Mathematics of computing → Mathematical optimization
  • 1 Networks → Control path algorithms
  • 1 Networks → Network performance evaluation
  • Show More...

  • Refine by Keyword
  • 1 ARRIVAL
  • 1 Algorithmic Game Theory
  • 1 Algorithms and Complexity of traffic equilibrium computations
  • 1 Approximation algorit
  • 1 Arrival
  • 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact