Search Results

Documents authored by Vetta, Adrian

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.43
Robot Positioning Using Torus Packing for Multisets

Authors: Chung Shue Chen, Peter Keevash, Sean Kennedy, Élie de Panafieu, and Adrian Vetta

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We consider the design of a positioning system where a robot determines its position from local observations. This is a well-studied problem of considerable practical importance and mathematical interest. The dominant paradigm derives from the classical theory of de Bruijn sequences, where the robot has access to a window within a larger code and can determine its position if these windows are distinct. We propose an alternative model in which the robot has more limited observational powers, which we argue is more realistic in terms of engineering: the robot does not have access to the full pattern of colours (or letters) in the window, but only to the intensity of each colour (or the number of occurrences of each letter). This leads to a mathematically interesting problem with a different flavour to that arising in the classical paradigm, requiring new construction techniques. The parameters of our construction are optimal up to a constant factor, and computing the position requires only a constant number of arithmetic operations.
Cite as

Chung Shue Chen, Peter Keevash, Sean Kennedy, Élie de Panafieu, and Adrian Vetta. Robot Positioning Using Torus Packing for Multisets. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2024.43,
  author =	{Chen, Chung Shue and Keevash, Peter and Kennedy, Sean and de Panafieu, \'{E}lie and Vetta, Adrian},
  title =	{{Robot Positioning Using Torus Packing for Multisets}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{43:1--43:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.43},
  URN =		{urn:nbn:de:0030-drops-201862},
  doi =		{10.4230/LIPIcs.ICALP.2024.43},
  annote =	{Keywords: Universal cycles, positioning systems, de Bruijn sequences}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.28
One n Remains to Settle the Tree Conjecture

Authors: Jack Dippel and Adrian Vetta

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
In the famous network creation game of Fabrikant et al. [Fabrikant et al., 2003] a set of agents play a game to build a connected graph. The n agents form the vertex set V of the graph and each vertex v ∈ V buys a set E_v of edges inducing a graph G = (V,⋃_{v∈V} E_v). The private objective of each vertex is to minimize the sum of its building cost (the cost of the edges it buys) plus its connection cost (the total distance from itself to every other vertex). Given a cost of α for each individual edge, a long-standing conjecture, called the tree conjecture, states that if α > n then every Nash equilibrium graph in the game is a spanning tree. After a plethora of work, it is known that the conjecture holds for any α > 3n-3. In this paper we prove the tree conjecture holds for α > 2n. This reduces by half the open range for α with only (n-3, 2n) remaining in order to settle the conjecture.
Cite as

Jack Dippel and Adrian Vetta. One n Remains to Settle the Tree Conjecture. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dippel_et_al:LIPIcs.STACS.2024.28,
  author =	{Dippel, Jack and Vetta, Adrian},
  title =	{{One n Remains to Settle the Tree Conjecture}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.28},
  URN =		{urn:nbn:de:0030-drops-197388},
  doi =		{10.4230/LIPIcs.STACS.2024.28},
  annote =	{Keywords: Algorithmic Game Theory, Network Creation Games, Tree Conjecture}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.78
Large Supports are Required for Well-Supported Nash Equilibria

Authors: Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta, and Hehui Wu

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

Abstract
We prove that for any constant k and any epsilon < 1, there exist bimatrix win-lose games for which every epsilon-WSNE requires supports of cardinality greater than k. To do this, we provide a graph-theoretic characterization of win-lose games that possess epsilon-WSNE with constant cardinality supports. We then apply a result in additive number theory of Haight to construct win-lose games that do not satisfy the requirements of the characterization. These constructions disprove graph theoretic conjectures of Daskalakis, Mehta and Papadimitriou and Myers.
Cite as

Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta, and Hehui Wu. Large Supports are Required for Well-Supported Nash Equilibria. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 78-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{anbalagan_et_al:LIPIcs.APPROX-RANDOM.2015.78,
  author =	{Anbalagan, Yogesh and Huang, Hao and Lovett, Shachar and Norin, Sergey and Vetta, Adrian and Wu, Hehui},
  title =	{{Large Supports are Required for Well-Supported Nash Equilibria}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{78--84},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.78},
  URN =		{urn:nbn:de:0030-drops-52959},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.78},
  annote =	{Keywords: bimatrix games, well-supported Nash equilibria}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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