29 Search Results for "G�rtner, Bernd"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.69
A Subexponential Algorithm for ARRIVAL

Authors: Bernd Gärtner, Sebastian Haslebacher, and Hung P. Hoang

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
The ARRIVAL problem is to decide the fate of a train moving along the edges of a directed graph, according to a simple (deterministic) pseudorandom walk. The problem is in NP∩coNP but not known to be in 𝖯. The currently best algorithms have runtime 2^Θ(n) where n is the number of vertices. This is not much better than just performing the pseudorandom walk. We develop a subexponential algorithm with runtime 2^O(√nlog n). We also give a polynomial-time algorithm if the graph is almost acyclic. Both results are derived from a new general approach to solve ARRIVAL instances.
Cite as

Bernd Gärtner, Sebastian Haslebacher, and Hung P. Hoang. A Subexponential Algorithm for ARRIVAL. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gartner_et_al:LIPIcs.ICALP.2021.69,
  author =	{G\"{a}rtner, Bernd and Haslebacher, Sebastian and Hoang, Hung P.},
  title =	{{A Subexponential Algorithm for ARRIVAL}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{69:1--69:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.69},
  URN =		{urn:nbn:de:0030-drops-141387},
  doi =		{10.4230/LIPIcs.ICALP.2021.69},
  annote =	{Keywords: Pseudorandom walks, reachability, graph games, switching systems}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.5
Two Phase Transitions in Two-Way Bootstrap Percolation

Authors: Ahad N. Zehmakan

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
Consider a graph G and an initial random configuration, where each node is black with probability p and white otherwise, independently. In discrete-time rounds, each node becomes black if it has at least r black neighbors and white otherwise. We prove that this basic process exhibits a threshold behavior with two phase transitions when the underlying graph is a d-dimensional torus and identify the threshold values.
Cite as

Ahad N. Zehmakan. Two Phase Transitions in Two-Way Bootstrap Percolation. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{zehmakan:LIPIcs.ISAAC.2019.5,
  author =	{Zehmakan, Ahad N.},
  title =	{{Two Phase Transitions in Two-Way Bootstrap Percolation}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{5:1--5:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.5},
  URN =		{urn:nbn:de:0030-drops-115017},
  doi =		{10.4230/LIPIcs.ISAAC.2019.5},
  annote =	{Keywords: bootstrap percolation, cellular automata, phase transition, d-dimensional torus, r-threshold model, biased majority}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.COSIT.2019.4
Representation of Interdependencies Between Urban Networks by a Multi-Layer Graph (Short Paper)

Authors: Laura Pinson, Géraldine Del Mondo, and Pierrick Tranouez

Published in: LIPIcs, Volume 142, 14th International Conference on Spatial Information Theory (COSIT 2019)

Abstract
The RGC4 (Urban resilience and Crisis Management in a Context of Slow Flood to Slow Kinetics) project aims to develop tools to help manage critical technical networks as part of the management process of crisis in a context of slow kinetic flooding in Paris. This project focuses on cascading models to identify a number of inter-dependencies between networks and to define tools capable of coordinating the actions of managers before and during the crisis. This paper revisits the conceptual and methodological bases of networks approach to study the inter-dependencies between networks. Research that studies the return to service of infrastructure networks often angle it from the perspective of operational research. The article proposes a graph theory perspective based on a multi-layer network approach and shows how to characterize the inter-dependencies between networks at three process levels (macro, meso, micro)
Cite as

Laura Pinson, Géraldine Del Mondo, and Pierrick Tranouez. Representation of Interdependencies Between Urban Networks by a Multi-Layer Graph (Short Paper). In 14th International Conference on Spatial Information Theory (COSIT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 142, pp. 4:1-4:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{pinson_et_al:LIPIcs.COSIT.2019.4,
  author =	{Pinson, Laura and Del Mondo, G\'{e}raldine and Tranouez, Pierrick},
  title =	{{Representation of Interdependencies Between Urban Networks by a Multi-Layer Graph}},
  booktitle =	{14th International Conference on Spatial Information Theory (COSIT 2019)},
  pages =	{4:1--4:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-115-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{142},
  editor =	{Timpf, Sabine and Schlieder, Christoph and Kattenbeck, Markus and Ludwig, Bernd and Stewart, Kathleen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2019.4},
  URN =		{urn:nbn:de:0030-drops-110962},
  doi =		{10.4230/LIPIcs.COSIT.2019.4},
  annote =	{Keywords: graph theory, multi-layer network, inter-dependencies, urban networks, urban resilience}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.COSIT.2019.25
Assessing Spatial Information in Physical Environments (Short Paper)

Authors: Vinicius M. Netto, Edgardo Brigatti, Caio Cacholas, and Vinicius Gomes Aleixo

Published in: LIPIcs, Volume 142, 14th International Conference on Spatial Information Theory (COSIT 2019)

Abstract
Many approaches have dealt with the hypothesis that the environment contain information, mostly focusing on how humans decode information from the environment in visual perception, navigation, and spatial decision-making. A question yet to be fully explored is how the built environment could encode forms of information in its own physical structures. This paper explores a new measure of spatial information, and applies it to twenty cities from different spatial cultures and regions of the world. Findings suggest that this methodology is able to identify similarities between cities, generating a classification scheme that opens up new questions about what we call "cultural hypothesis": the idea that spatial configurations find consistent differences between cultures and regions.
Cite as

Vinicius M. Netto, Edgardo Brigatti, Caio Cacholas, and Vinicius Gomes Aleixo. Assessing Spatial Information in Physical Environments (Short Paper). In 14th International Conference on Spatial Information Theory (COSIT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 142, pp. 25:1-25:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{netto_et_al:LIPIcs.COSIT.2019.25,
  author =	{Netto, Vinicius M. and Brigatti, Edgardo and Cacholas, Caio and Aleixo, Vinicius Gomes},
  title =	{{Assessing Spatial Information in Physical Environments}},
  booktitle =	{14th International Conference on Spatial Information Theory (COSIT 2019)},
  pages =	{25:1--25:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-115-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{142},
  editor =	{Timpf, Sabine and Schlieder, Christoph and Kattenbeck, Markus and Ludwig, Bernd and Stewart, Kathleen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2019.25},
  URN =		{urn:nbn:de:0030-drops-111179},
  doi =		{10.4230/LIPIcs.COSIT.2019.25},
  annote =	{Keywords: Spatial information, physical environment, Shannon entropy}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.38
The Crossing Tverberg Theorem

Authors: Radoslav Fulek, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2.
Cite as

Radoslav Fulek, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. The Crossing Tverberg Theorem. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fulek_et_al:LIPIcs.SoCG.2019.38,
  author =	{Fulek, Radoslav and G\"{a}rtner, Bernd and Kupavskii, Andrey and Valtr, Pavel and Wagner, Uli},
  title =	{{The Crossing Tverberg Theorem}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{38:1--38:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.38},
  URN =		{urn:nbn:de:0030-drops-104423},
  doi =		{10.4230/LIPIcs.SoCG.2019.38},
  annote =	{Keywords: Discrete geometry, Tverberg theorem, Crossing Tverberg theorem}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2018.1
Fault-tolerant Distributed Reactive Programming

Authors: Ragnar Mogk, Lars Baumgärtner, Guido Salvaneschi, Bernd Freisleben, and Mira Mezini

Published in: LIPIcs, Volume 109, 32nd European Conference on Object-Oriented Programming (ECOOP 2018)

Abstract
In this paper, we present a holistic approach to provide fault tolerance for distributed reactive programming. Our solution automatically stores and recovers program state to handle crashes, automatically updates and shares distributed parts of the state to provide eventual consistency, and handles errors in a fine-grained manner to allow precise manual control when necessary. By making use of the reactive programming paradigm, we provide these mechanisms without changing the behavior of existing programs and with reasonable performance, as indicated by our experimental evaluation.
Cite as

Ragnar Mogk, Lars Baumgärtner, Guido Salvaneschi, Bernd Freisleben, and Mira Mezini. Fault-tolerant Distributed Reactive Programming. In 32nd European Conference on Object-Oriented Programming (ECOOP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 109, pp. 1:1-1:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{mogk_et_al:LIPIcs.ECOOP.2018.1,
  author =	{Mogk, Ragnar and Baumg\"{a}rtner, Lars and Salvaneschi, Guido and Freisleben, Bernd and Mezini, Mira},
  title =	{{Fault-tolerant Distributed Reactive Programming}},
  booktitle =	{32nd European Conference on Object-Oriented Programming (ECOOP 2018)},
  pages =	{1:1--1:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-079-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{109},
  editor =	{Millstein, Todd},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2018.1},
  URN =		{urn:nbn:de:0030-drops-92064},
  doi =		{10.4230/LIPIcs.ECOOP.2018.1},
  annote =	{Keywords: reactive programming, distributed systems, CRDTs, snapshots, restoration, error handling, fault tolerance}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.60
ARRIVAL: Next Stop in CLS

Authors: Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubácek, Karel Král, Hagar Mosaad, and Veronika Slívová

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

Abstract
We study the computational complexity of Arrival, a zero-player game on n-vertex switch graphs introduced by Dohrau, Gärtner, Kohler, Matousek, and Welzl. They showed that the problem of deciding termination of this game is contained in NP n coNP. Karthik C. S. recently introduced a search variant of Arrival and showed that it is in the complexity class PLS. In this work, we significantly improve the known upper bounds for both the decision and the search variants of Arrival. First, we resolve a question suggested by Dohrau et al. and show that the decision variant of Arrival is in UP n coUP. Second, we prove that the search variant of Arrival is contained in CLS. Third, we give a randomized O(1.4143^n)-time algorithm to solve both variants. Our main technical contributions are (a) an efficiently verifiable characterization of the unique witness for termination of the Arrival game, and (b) an efficient way of sampling from the state space of the game. We show that the problem of finding the unique witness is contained in CLS, whereas it was previously conjectured to be FPSPACE-complete. The efficient sampling procedure yields the first algorithm for the problem that has expected runtime O(c^n) with c<2.
Cite as

Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubácek, Karel Král, Hagar Mosaad, and Veronika Slívová. ARRIVAL: Next Stop in CLS. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 60:1-60:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gartner_et_al:LIPIcs.ICALP.2018.60,
  author =	{G\"{a}rtner, Bernd and Hansen, Thomas Dueholm and Hub\'{a}cek, Pavel and Kr\'{a}l, Karel and Mosaad, Hagar and Sl{\'\i}vov\'{a}, Veronika},
  title =	{{ARRIVAL: Next Stop in CLS}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{60:1--60:13},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.60},
  URN =		{urn:nbn:de:0030-drops-90641},
  doi =		{10.4230/LIPIcs.ICALP.2018.60},
  annote =	{Keywords: CLS, switch graphs, zero-player game, UP n coUP}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2017.28
Synthesis in Distributed Environments

Authors: Bernd Finkbeiner and Paul Gölz

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract
Most approaches to the synthesis of reactive systems study the problem in terms of a two-player game with complete observation. In many applications, however, the system's environment consists of several distinct entities, and the system must actively communicate with these entities in order to obtain information available in the environment. In this paper, we model such environments as a team of players and keep track of the information known to each individual player. This allows us to synthesize programs that interact with a distributed environment and leverage multiple interacting sources of information. The synthesis problem in distributed environments corresponds to solving a special class of Petri games, i.e., multi-player games played over Petri nets, where the net has a distinguished token representing the system and an arbitrary number of tokens representing the environment. While, in general, even the decidability of Petri games is an open question, we show that the synthesis problem in distributed environments can be solved in polynomial time for nets with up to two environment tokens. For an arbitrary but fixed number of three or more environment tokens, the problem is NP-complete. If the number of environment tokens grows with the size of the net, the problem is EXPTIME-complete.
Cite as

Bernd Finkbeiner and Paul Gölz. Synthesis in Distributed Environments. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{finkbeiner_et_al:LIPIcs.FSTTCS.2017.28,
  author =	{Finkbeiner, Bernd and G\"{o}lz, Paul},
  title =	{{Synthesis in Distributed Environments}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{28:1--28:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.28},
  URN =		{urn:nbn:de:0030-drops-84068},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.28},
  annote =	{Keywords: reactive synthesis, distributed information, causal memory, Petri nets}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.30
The Niceness of Unique Sink Orientations

Authors: Bernd Gärtner and Antonis Thomas

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

Abstract
Random Edge is the most natural randomized pivot rule for the simplex algorithm. Considerable progress has been made recently towards fully understanding its behavior. Back in 2001, Welzl introduced the concepts of reachmaps and niceness of Unique Sink Orientations (USO), in an effort to better understand the behavior of Random Edge. In this paper, we initiate the systematic study of these concepts. We settle the questions that were asked by Welzl about the niceness of (acyclic) USO. Niceness implies natural upper bounds for Random Edge and we provide evidence that these are tight or almost tight in many interesting cases. Moreover, we show that Random Edge is polynomial on at least n^{Omega(2^n)} many (possibly cyclic) USO. As a bonus, we describe a derandomization of Random Edge which achieves the same asymptotic upper bounds with respect to niceness.
Cite as

Bernd Gärtner and Antonis Thomas. The Niceness of Unique Sink Orientations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{gartner_et_al:LIPIcs.APPROX-RANDOM.2016.30,
  author =	{G\"{a}rtner, Bernd and Thomas, Antonis},
  title =	{{The Niceness of Unique Sink Orientations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{30:1--30:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.30},
  URN =		{urn:nbn:de:0030-drops-66538},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.30},
  annote =	{Keywords: random edge, unique sink orientation, random walk, reachmap, niceness}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.40
Random Sampling with Removal

Authors: Bernd Gärtner, Johannes Lengler, and May Szedlák

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Random sampling is a classical tool in constrained optimization. Under favorable conditions, the optimal solution subject to a small subset of randomly chosen constraints violates only a small subset of the remaining constraints. Here we study the following variant that we call random sampling with removal: suppose that after sampling the subset, we remove a fixed number of constraints from the sample, according to an arbitrary rule. Is it still true that the optimal solution of the reduced sample violates only a small subset of the constraints? The question naturally comes up in situations where the solution subject to the sampled constraints is used as an approximate solution to the original problem. In this case, it makes sense to improve cost and volatility of the sample solution by removing some of the constraints that appear most restricting. At the same time, the approximation quality (measured in terms of violated constraints) should remain high. We study random sampling with removal in a generalized, completely abstract setting where we assign to each subset R of the constraints an arbitrary set V(R) of constraints disjoint from R; in applications, V(R) corresponds to the constraints violated by the optimal solution subject to only the constraints in R. Furthermore, our results are parametrized by the dimension d, i.e., we assume that every set R has a subset B of size at most d with the same set of violated constraints. This is the first time this generalized setting is studied. In this setting, we prove matching upper and lower bounds for the expected number of constraints violated by a random sample, after the removal of k elements. For a large range of values of k, the new upper bounds improve the previously best bounds for LP-type problems, which moreover had only been known in special cases. We show that this bound on special LP-type problems, can be derived in the much more general setting of violator spaces, and with very elementary proofs.
Cite as

Bernd Gärtner, Johannes Lengler, and May Szedlák. Random Sampling with Removal. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{gartner_et_al:LIPIcs.SoCG.2016.40,
  author =	{G\"{a}rtner, Bernd and Lengler, Johannes and Szedl\'{a}k, May},
  title =	{{Random Sampling with Removal}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.40},
  URN =		{urn:nbn:de:0030-drops-59328},
  doi =		{10.4230/LIPIcs.SoCG.2016.40},
  annote =	{Keywords: LP-type problem, violator space, random sampling, sampling with removal}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.315
Combinatorial Redundancy Detection

Authors: Komei Fukuda, Bernd Gärtner, and May Szedlák

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
The problem of detecting and removing redundant constraints is fundamental in optimization. We focus on the case of linear programs (LPs) in dictionary form, given by n equality constraints in n+d variables, where the variables are constrained to be nonnegative. A variable x_r is called redundant, if after removing its nonnegativity constraint the LP still has the same feasible region. The time needed to solve such an LP is denoted by LP(n,d). It is easy to see that solving n+d LPs of the above size is sufficient to detect all redundancies. The currently fastest practical method is the one by Clarkson: it solves n+d linear programs, but each of them has at most s variables, where s is the number of nonredundant constraints. In the first part we show that knowing all of the finitely many dictionaries of the LP is sufficient for the purpose of redundancy detection. A dictionary is a matrix that can be thought of as an enriched encoding of a vertex in the LP. Moreover - and this is the combinatorial aspect - it is enough to know only the signs of the entries, the actual values do not matter. Concretely we show that for any variable x_r one can find a dictionary, such that its sign pattern is either a redundancy or nonredundancy certificate for x_r. In the second part we show that considering only the sign patterns of the dictionary, there is an output sensitive algorithm of running time of order d (n+d) s^{d-1} LP(s,d) + d s^{d} LP(n,d) to detect all redundancies. In the case where all constraints are in general position, the running time is of order s LP(n,d) + (n+d) LP(s,d), which is essentially the running time of the Clarkson method. Our algorithm extends naturally to a more general setting of arrangements of oriented topological hyperplane arrangements.
Cite as

Komei Fukuda, Bernd Gärtner, and May Szedlák. Combinatorial Redundancy Detection. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 315-328, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{fukuda_et_al:LIPIcs.SOCG.2015.315,
  author =	{Fukuda, Komei and G\"{a}rtner, Bernd and Szedl\'{a}k, May},
  title =	{{Combinatorial Redundancy Detection}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{315--328},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.315},
  URN =		{urn:nbn:de:0030-drops-51434},
  doi =		{10.4230/LIPIcs.SOCG.2015.315},
  annote =	{Keywords: system of linear inequalities, redundancy removal, linear programming, output sensitive algorithm, Clarkson’s method}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.341
The Complexity of Recognizing Unique Sink Orientations

Authors: Bernd Gärtner and Antonis Thomas

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
Given a Boolean Circuit with n inputs and n outputs, we want to decide if it represents a Unique Sink Orientation (USO). USOs are useful combinatorial objects that serve as abstraction of many relevant optimization problems. We prove that recognizing a USO is coNP-complete. However, the situation appears to be more complicated for recognizing acyclic USOs. Firstly, we give a construction to prove that there exist cyclic USOs where the smallest cycle is of superpolynomial size. This implies that the straightforward representation of a cycle (i.e. by a list of vertices) does not make up for a coNP certificate. Inspired by this fact, we investigate the connection of recognizing an acyclic USO to PSPACE and we prove that the problem is PSPACE-complete.
Cite as

Bernd Gärtner and Antonis Thomas. The Complexity of Recognizing Unique Sink Orientations. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 341-353, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{gartner_et_al:LIPIcs.STACS.2015.341,
  author =	{G\"{a}rtner, Bernd and Thomas, Antonis},
  title =	{{The Complexity of Recognizing Unique Sink Orientations}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{341--353},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.341},
  URN =		{urn:nbn:de:0030-drops-49252},
  doi =		{10.4230/LIPIcs.STACS.2015.341},
  annote =	{Keywords: complexity, recognizing, unique sink orientations, coNP, PSPACE}
}
Document
DOI: 10.4230/DagRep.4.2.79
Robots Learning from Experiences (Dagstuhl Seminar 14081)

Authors: Anthony G. Cohn, Bernd Neumann, Alessandro Saffiotti, and Markus Vincze

Published in: Dagstuhl Reports, Volume 4, Issue 2 (2014)

Abstract
This report documents the programme and the outcomes of Dagstuhl Seminar 14081 "Robots Learning from Experiences". The report begins with a summary comprising information about the seminar topics, the programme, important discussion points, and conclusions. The main body of the report consists of the abstracts of 25 presentations given at the seminar, and of four reports about discussion groups.
Cite as

Anthony G. Cohn, Bernd Neumann, Alessandro Saffiotti, and Markus Vincze. Robots Learning from Experiences (Dagstuhl Seminar 14081). In Dagstuhl Reports, Volume 4, Issue 2, pp. 79-109, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{cohn_et_al:DagRep.4.2.79,
  author =	{Cohn, Anthony G. and Neumann, Bernd and Saffiotti, Alessandro and Vincze, Markus},
  title =	{{Robots Learning from Experiences (Dagstuhl Seminar 14081)}},
  pages =	{79--109},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{2},
  editor =	{Cohn, Anthony G. and Neumann, Bernd and Saffiotti, Alessandro and Vincze, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.2.79},
  URN =		{urn:nbn:de:0030-drops-45465},
  doi =		{10.4230/DagRep.4.2.79},
  annote =	{Keywords: Learning, experiences, cognitive systems}
}
Document
DOI: 10.4230/DagSemProc.08091.1
08091 Abstracts Collection – Logic and Probability for Scene Interpretation

Authors: Bernd Neumann, Anthony C. Cohn, David C. Hogg, and Ralf Möller

Published in: Dagstuhl Seminar Proceedings, Volume 8091, Logic and Probability for Scene Interpretation (2008)

Abstract
From 25.2.2008 to Friday 29.2.2008, the Dagstuhl Seminar 08091 ``Logic and Probability for Scene Interpretation'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper.
Cite as

Bernd Neumann, Anthony C. Cohn, David C. Hogg, and Ralf Möller. 08091 Abstracts Collection – Logic and Probability for Scene Interpretation. In Logic and Probability for Scene Interpretation. Dagstuhl Seminar Proceedings, Volume 8091, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{neumann_et_al:DagSemProc.08091.1,
  author =	{Neumann, Bernd and Cohn, Anthony C. and Hogg, David C. and M\"{o}ller, Ralf},
  title =	{{08091 Abstracts Collection – Logic and Probability for Scene Interpretation}},
  booktitle =	{Logic and Probability for Scene Interpretation},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8091},
  editor =	{Anthony G. Cohn and David C. Hogg and Ralf M\"{o}ller and Bernd Neumann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08091.1},
  URN =		{urn:nbn:de:0030-drops-16480},
  doi =		{10.4230/DagSemProc.08091.1},
  annote =	{Keywords: Logic, probabilities, scene interpretation}
}
Document
DOI: 10.4230/DagSemProc.08091.4
Architectural and Representational Requirements for Seeing Processes, Proto-affordances and Affordances

Authors: Aaron Sloman

Published in: Dagstuhl Seminar Proceedings, Volume 8091, Logic and Probability for Scene Interpretation (2008)

Abstract
This paper, combining the standpoints of philosophy and Artificial Intelligence with theoretical psychology, summarises several decades of investigation by the author of the variety of functions of vision in humans and other animals, pointing out that biological evolution has solved many more problems than are normally noticed. For example, the biological functions of human and animal vision are closely related to the ability of humans to do mathematics, including discovering and proving theorems in geometry, topology and arithmetic. Many of the phenomena discovered by psychologists and neuroscientists require sophisticated controlled laboratory settings and specialised measuring equipment, whereas the functions of vision reported here mostly require only careful attention to a wide range of everyday competences that easily go unnoticed. Currently available computer models and neural theories are very far from explaining those functions, so progress in explaining how vision works is more in need of new proposals for explanatory mechanisms than new laboratory data. Systematically formulating the requirements for such mechanisms is not easy. If we start by analysing familiar competences, that can suggest new experiments to clarify precise forms of these competences, how they develop within individuals, which other species have them, and how performance varies according to conditions. This will help to constrain requirements for models purporting to explain how the competences work. For example, Gibson’s theory of affordances needs a number of extensions, including allowing affordances to be composed in several ways from lower level proto-affordances. The paper ends with speculations regarding the need for new kinds of information-processing machinery to account for the phenomena.
Cite as

Aaron Sloman. Architectural and Representational Requirements for Seeing Processes, Proto-affordances and Affordances. In Logic and Probability for Scene Interpretation. Dagstuhl Seminar Proceedings, Volume 8091, pp. 1-57, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{sloman:DagSemProc.08091.4,
  author =	{Sloman, Aaron},
  title =	{{Architectural and Representational Requirements for Seeing Processes, Proto-affordances and Affordances}},
  booktitle =	{Logic and Probability for Scene Interpretation},
  pages =	{1--57},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8091},
  editor =	{Anthony G. Cohn and David C. Hogg and Ralf M\"{o}ller and Bernd Neumann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08091.4},
  URN =		{urn:nbn:de:0030-drops-16569},
  doi =		{10.4230/DagSemProc.08091.4},
  annote =	{Keywords: Vision, affordances, architectures, development, design space}
}
  • Refine by Author
  • 7 Gärtner, Bernd
  • 3 Möller, Ralf
  • 3 Neumann, Bernd
  • 2 Szedlák, May
  • 2 Thomas, Antonis
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Decision analysis
  • 1 Applied computing → Operations research
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Social and professional topics
  • 1 Social and professional topics → Cultural characteristics
  • Show More...

  • Refine by Keyword
  • 2 Logic
  • 2 Scene interpretation
  • 2 Vision
  • 1 Abstraction
  • 1 Autonomous Driving;
  • Show More...

  • Refine by Type
  • 29 document

  • Refine by Publication Year
  • 16 2008
  • 4 2019
  • 3 2018
  • 2 2015
  • 2 2016
  • Show More...

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