3 Search Results for "Dippel, Jack"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.96
Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets

Authors: Yasushi Kawase, Koichi Nishimura, and Hanna Sumita

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

Abstract
We study the problem of minimizing a given symmetric strictly convex function over the Minkowski sum of an integral base-polyhedron and an M-convex set. This problem has a hybrid of continuous and discrete structures. This emerges from the problem of allocating mixed goods, consisting of both divisible and indivisible goods, to agents with binary valuations so that the fairness measure, such as the Nash welfare, is maximized. It is known that both an integral base-polyhedron and an M-convex set have similar and nice properties, and the non-hybrid case can be solved in polynomial time. While the hybrid case lacks some of these properties, we show the structure of an optimal solution. Moreover, we exploit a proximity inherent in the problem. Through our findings, we demonstrate that our problem is NP-hard even in the fair allocation setting where all indivisible goods are identical. Moreover, we provide a polynomial-time algorithm for the fair allocation problem when all divisible goods are identical.
Cite as

Yasushi Kawase, Koichi Nishimura, and Hanna Sumita. Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 96:1-96:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.ICALP.2024.96,
  author =	{Kawase, Yasushi and Nishimura, Koichi and Sumita, Hanna},
  title =	{{Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{96:1--96:19},
  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.96},
  URN =		{urn:nbn:de:0030-drops-202393},
  doi =		{10.4230/LIPIcs.ICALP.2024.96},
  annote =	{Keywords: Integral base-polyhedron, Fair allocation, Matroid}
}
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.ISAAC.2021.38
An Improved Approximation Algorithm for the Matching Augmentation Problem

Authors: Joseph Cheriyan, Robert Cummings, Jack Dippel, and Jasper Zhu

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We present a 5/3-approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. A 7/4-approximation algorithm for the same problem was presented recently, see Cheriyan, et al., "The matching augmentation problem: a 7/4-approximation algorithm," Math. Program., 182(1):315-354, 2020. Our improvement is based on new algorithmic techniques, and some of these may lead to advances on related problems.
Cite as

Joseph Cheriyan, Robert Cummings, Jack Dippel, and Jasper Zhu. An Improved Approximation Algorithm for the Matching Augmentation Problem. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cheriyan_et_al:LIPIcs.ISAAC.2021.38,
  author =	{Cheriyan, Joseph and Cummings, Robert and Dippel, Jack and Zhu, Jasper},
  title =	{{An Improved Approximation Algorithm for the Matching Augmentation Problem}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{38:1--38:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.38},
  URN =		{urn:nbn:de:0030-drops-154714},
  doi =		{10.4230/LIPIcs.ISAAC.2021.38},
  annote =	{Keywords: 2-Edge connected graph, 2-edge covers, approximation algorithms, connectivity augmentation, forest augmentation problem, matching augmentation problem, network design}
}
  • Refine by Author
  • 2 Dippel, Jack
  • 1 Cheriyan, Joseph
  • 1 Cummings, Robert
  • 1 Kawase, Yasushi
  • 1 Nishimura, Koichi
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Algorithmic game theory
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Social networks

  • Refine by Keyword
  • 1 2-Edge connected graph
  • 1 2-edge covers
  • 1 Algorithmic Game Theory
  • 1 Fair allocation
  • 1 Integral base-polyhedron
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2024
  • 1 2021

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact