5 Search Results for "Bertschinger, Daniel"

Document
DOI: 10.4230/LIPIcs.SWAT.2022.16
Well-Separation and Hyperplane Transversals in High Dimensions

Authors: Helena Bergold, Daniel Bertschinger, Nicolas Grelier, Wolfgang Mulzer, and Patrick Schnider

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
A family of k point sets in d dimensions is well-separated if the convex hulls of any two disjoint subfamilies can be separated by a hyperplane. Well-separation is a strong assumption that allows us to conclude that certain kinds of generalized ham-sandwich cuts for the point sets exist. But how hard is it to check if a given family of high-dimensional point sets has this property? Starting from this question, we study several algorithmic aspects of the existence of transversals and separations in high-dimensions. First, we give an explicit proof that k point sets are well-separated if and only if their convex hulls admit no (k - 2)-transversal, i.e., if there exists no (k - 2)-dimensional flat that intersects the convex hulls of all k sets. It follows that the task of checking well-separation lies in the complexity class coNP. Next, we show that it is NP-hard to decide whether there is a hyperplane-transversal (that is, a (d - 1)-transversal) of a family of d + 1 line segments in ℝ^d, where d is part of the input. As a consequence, it follows that the general problem of testing well-separation is coNP-complete. Furthermore, we show that finding a hyperplane that maximizes the number of intersected sets is NP-hard, but allows for an Ω((log k)/(k log log k))-approximation algorithm that is polynomial in d and k, when each set consists of a single point. When all point sets are finite, we show that checking whether there exists a (k - 2)-transversal is in fact strongly NP-complete. Finally, we take the viewpoint of parametrized complexity, using the dimension d as a parameter: given k convex sets in ℝ^d, checking whether there is a (k-2)-transversal is FPT with respect to d. On the other hand, for k ≥ d+1 finite point sets in ℝ^d, it turns out that checking whether there is a (d-1)-transversal is W[1]-hard with respect to d.
Cite as

Helena Bergold, Daniel Bertschinger, Nicolas Grelier, Wolfgang Mulzer, and Patrick Schnider. Well-Separation and Hyperplane Transversals in High Dimensions. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bergold_et_al:LIPIcs.SWAT.2022.16,
  author =	{Bergold, Helena and Bertschinger, Daniel and Grelier, Nicolas and Mulzer, Wolfgang and Schnider, Patrick},
  title =	{{Well-Separation and Hyperplane Transversals in High Dimensions}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.16},
  URN =		{urn:nbn:de:0030-drops-161766},
  doi =		{10.4230/LIPIcs.SWAT.2022.16},
  annote =	{Keywords: hyperplane transversal, high-dimension, hardness}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.17
Lions and Contamination: Monotone Clearings

Authors: Daniel Bertschinger, Meghana M. Reddy, and Enrico Mann

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
We consider a special variant of a pursuit-evasion game called lions and contamination. In a graph whose vertices are originally contaminated, a set of lions walk around the graph and clear the contamination from every vertex they visit. The contamination, however, simultaneously spreads to any adjacent vertex not occupied by a lion. We study the relationship between different types of clearings of graphs, such as clearings which do not allow recontamination, clearings where at most one lion moves at each time step and clearings where lions are forbidden to be stacked on the same vertex. We answer several questions raised by Adams et al. [H. Adams et al., 2020].
Cite as

Daniel Bertschinger, Meghana M. Reddy, and Enrico Mann. Lions and Contamination: Monotone Clearings. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 17:1-17:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bertschinger_et_al:LIPIcs.SWAT.2022.17,
  author =	{Bertschinger, Daniel and M. Reddy, Meghana and Mann, Enrico},
  title =	{{Lions and Contamination: Monotone Clearings}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{17:1--17:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.17},
  URN =		{urn:nbn:de:0030-drops-161778},
  doi =		{10.4230/LIPIcs.SWAT.2022.17},
  annote =	{Keywords: Algorithmic Games, Pursuit-Evasion Games, Graph Contamination, Clearings}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.17
An Optimal Decentralized (Δ + 1)-Coloring Algorithm

Authors: Daniel Bertschinger, Johannes Lengler, Anders Martinsson, Robert Meier, Angelika Steger, Miloš Trujić, and Emo Welzl

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Consider the following simple coloring algorithm for a graph on n vertices. Each vertex chooses a color from {1, ..., Δ(G) + 1} uniformly at random. While there exists a conflicted vertex choose one such vertex uniformly at random and recolor it with a randomly chosen color. This algorithm was introduced by Bhartia et al. [MOBIHOC'16] for channel selection in WIFI-networks. We show that this algorithm always converges to a proper coloring in expected O(n log Δ) steps, which is optimal and proves a conjecture of Chakrabarty and de Supinski [SOSA'20].
Cite as

Daniel Bertschinger, Johannes Lengler, Anders Martinsson, Robert Meier, Angelika Steger, Miloš Trujić, and Emo Welzl. An Optimal Decentralized (Δ + 1)-Coloring Algorithm. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bertschinger_et_al:LIPIcs.ESA.2020.17,
  author =	{Bertschinger, Daniel and Lengler, Johannes and Martinsson, Anders and Meier, Robert and Steger, Angelika and Truji\'{c}, Milo\v{s} and Welzl, Emo},
  title =	{{An Optimal Decentralized (\Delta + 1)-Coloring Algorithm}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{17:1--17:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.17},
  URN =		{urn:nbn:de:0030-drops-128837},
  doi =		{10.4230/LIPIcs.ESA.2020.17},
  annote =	{Keywords: Decentralized Algorithm, Distributed Computing, Graph Coloring, Randomized Algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.67
Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips)

Authors: Uli Wagner and Emo Welzl

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
Given a finite point set P in general position in the plane, a full triangulation is a maximal straight-line embedded plane graph on P. A partial triangulation on P is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge, removes a non-extreme point of degree 3, or adds a point in P ⧵ P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The goal of this paper is to investigate the structure of this graph, with emphasis on its connectivity. For sets P of n points in general position, we show that the bistellar flip graph is (n-3)-connected, thereby answering, for sets in general position, an open questions raised in a book (by De Loera, Rambau, and Santos) and a survey (by Lee and Santos) on triangulations. This matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points and projecting the lower convex hull), where (n-3)-connectivity has been known since the late 1980s through the secondary polytope (Gelfand, Kapranov, Zelevinsky) and Balinski’s Theorem. Our methods also yield the following results (see the full version [Wagner and Welzl, 2020]): (i) The bistellar flip graph can be covered by graphs of polytopes of dimension n-3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n-3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations are regular iff the trivial subdivision has height n-3 in the partial order of partial subdivisions. (iv) There are arbitrarily large sets P with non-regular partial triangulations, while every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular partial triangulations (answering a question by F. Santos in the unexpected direction).
Cite as

Uli Wagner and Emo Welzl. Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 67:1-67:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{wagner_et_al:LIPIcs.SoCG.2020.67,
  author =	{Wagner, Uli and Welzl, Emo},
  title =	{{Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips)}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{67:1--67:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.67},
  URN =		{urn:nbn:de:0030-drops-122259},
  doi =		{10.4230/LIPIcs.SoCG.2020.67},
  annote =	{Keywords: triangulation, flip graph, graph connectivity, associahedron, subdivision, convex decomposition, flippable edge, flip complex, regular triangulation, bistellar flip graph, secondary polytope, polyhedral subdivision}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.46
Strategic Payments in Financial Networks

Authors: Nils Bertschinger, Martin Hoefer, and Daniel Schmand

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
In their seminal work on systemic risk in financial markets, Eisenberg and Noe [Larry Eisenberg and Thomas Noe, 2001] proposed and studied a model with n firms embedded into a network of debt relations. We analyze this model from a game-theoretic point of view. Every firm is a rational agent in a directed graph that has an incentive to allocate payments in order to clear as much of its debt as possible. Each edge is weighted and describes a liability between the firms. We consider several variants of the game that differ in the permissible payment strategies. We study the existence and computational complexity of pure Nash and strong equilibria, and we provide bounds on the (strong) prices of anarchy and stability for a natural notion of social welfare. Our results highlight the power of financial regulation - if payments of insolvent firms can be centrally assigned, a socially optimal strong equilibrium can be found in polynomial time. In contrast, worst-case strong equilibria can be a factor of Ω(n) away from optimal, and, in general, computing a best response is an NP-hard problem. For less permissible sets of strategies, we show that pure equilibria might not exist, and deciding their existence as well as computing them if they exist constitute NP-hard problems.
Cite as

Nils Bertschinger, Martin Hoefer, and Daniel Schmand. Strategic Payments in Financial Networks. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 46:1-46:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bertschinger_et_al:LIPIcs.ITCS.2020.46,
  author =	{Bertschinger, Nils and Hoefer, Martin and Schmand, Daniel},
  title =	{{Strategic Payments in Financial Networks}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{46:1--46:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.46},
  URN =		{urn:nbn:de:0030-drops-117316},
  doi =		{10.4230/LIPIcs.ITCS.2020.46},
  annote =	{Keywords: Nash Equilibrium, Financial Network, Systemic Risk, Price of Anarchy, Equilibrium Computation}
}
  • Refine by Author
  • 3 Bertschinger, Daniel
  • 2 Welzl, Emo
  • 1 Bergold, Helena
  • 1 Bertschinger, Nils
  • 1 Grelier, Nicolas
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Computational geometry
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Graph coloring
  • 1 Mathematics of computing → Probabilistic algorithms
  • Show More...

  • Refine by Keyword
  • 1 Algorithmic Games
  • 1 Clearings
  • 1 Decentralized Algorithm
  • 1 Distributed Computing
  • 1 Equilibrium Computation
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 3 2020
  • 2 2022

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 Imprint Privacy Contact