Search Results

Documents authored by Krejca, Martin S.

Document
DOI: 10.4230/DagRep.14.6.215
Theory of Randomized Optimization Heuristics (Dagstuhl Seminar 24271)

Authors: Anne Auger, Tobias Glasmachers, Martin S. Krejca, Johannes Lengler, and Alexander Jungeilges

Published in: Dagstuhl Reports, Volume 14, Issue 6 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 24271 "Theory of Randomized Optimization Heuristics", which marks the twelfth installment of our biennial seminar series. This iteration saw a lot of discussion on important, yet rarely analyzed topics in the domain of heuristic optimization, such as mixed-integer problems, permutation spaces, and coevolution. Moreover, it aimed at unifying existing results by discussing mathematical tools (such as drift analysis), the structure of discrete problems, and a common framework for theoretical analysis and practical implementation. Last, more recent and important topics, such as constrained and multi-objective optimization, were a major part of the seminar. We had a vivid exchange in various breakout sessions and different talks, with a great mix of junior and senior participants, which was very positively received.
Cite as

Anne Auger, Tobias Glasmachers, Martin S. Krejca, Johannes Lengler, and Alexander Jungeilges. Theory of Randomized Optimization Heuristics (Dagstuhl Seminar 24271). In Dagstuhl Reports, Volume 14, Issue 6, pp. 215-244, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{auger_et_al:DagRep.14.6.215,
  author =	{Auger, Anne and Glasmachers, Tobias and Krejca, Martin S. and Lengler, Johannes and Jungeilges, Alexander},
  title =	{{Theory of Randomized Optimization Heuristics (Dagstuhl Seminar 24271)}},
  pages =	{215--244},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{14},
  number =	{6},
  editor =	{Auger, Anne and Glasmachers, Tobias and Krejca, Martin S. and Lengler, Johannes and Jungeilges, Alexander},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.14.6.215},
  URN =		{urn:nbn:de:0030-drops-227286},
  doi =		{10.4230/DagRep.14.6.215},
  annote =	{Keywords: Black-Box Optimization Heuristics, Evolution Strategies, Genetic and Evolutionary Algorithms, Runtime and Convergence Analysis, Stochastic Processes}
}
Document
DOI: 10.4230/DagRep.13.8.46
Synergizing Theory and Practice of Automated Algorithm Design for Optimization (Dagstuhl Seminar 23332)

Authors: Diederick Vermetten, Martin S. Krejca, Marius Lindauer, Manuel López-Ibáñez, and Katherine M. Malan

Published in: Dagstuhl Reports, Volume 13, Issue 8 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23332, which focused on automated algorithm design (AAD) for optimization. AAD aims to propose good algorithms and/or parameters thereof for optimization problems in an automated fashion, instead of forcing this decision on the user. As such, AAD is applicable in a variety of domains. The seminar brought together a diverse, international set of researchers from AAD and closely related fields. Especially, we invited people from both the empirical and the theoretical domain. A main goal of the seminar was to enable vivid discussions between these two groups in order to synergize the knowledge from either domain, thus advancing the area of AAD as a whole, and to reduce the gap between theory and practice. Over the course of the seminar, a good mix of breakout sessions and talks took place, which were very well received and which we detail in this report. Efforts to synergize theory and practice bore some fruit, and other important aspects of AAD were highlighted and discussed. Overall, the seminar was a huge success.
Cite as

Diederick Vermetten, Martin S. Krejca, Marius Lindauer, Manuel López-Ibáñez, and Katherine M. Malan. Synergizing Theory and Practice of Automated Algorithm Design for Optimization (Dagstuhl Seminar 23332). In Dagstuhl Reports, Volume 13, Issue 8, pp. 46-70, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{vermetten_et_al:DagRep.13.8.46,
  author =	{Vermetten, Diederick and Krejca, Martin S. and Lindauer, Marius and L\'{o}pez-Ib\'{a}\~{n}ez, Manuel and Malan, Katherine M.},
  title =	{{Synergizing Theory and Practice of Automated Algorithm Design for Optimization (Dagstuhl Seminar 23332)}},
  pages =	{46--70},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{8},
  editor =	{Vermetten, Diederick and Krejca, Martin S. and Lindauer, Marius and L\'{o}pez-Ib\'{a}\~{n}ez, Manuel and Malan, Katherine M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.8.46},
  URN =		{urn:nbn:de:0030-drops-198128},
  doi =		{10.4230/DagRep.13.8.46},
  annote =	{Keywords: automated algorithm design, hyper-parameter tuning, parameter control, heuristic optimization, black-box optimization}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.29
The Impact of Geometry on Monochrome Regions in the Flip Schelling Process

Authors: Thomas Bläsius, Tobias Friedrich, Martin S. Krejca, and Louise Molitor

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

Abstract
Schelling’s classical segregation model gives a coherent explanation for the wide-spread phenomenon of residential segregation. We introduce an agent-based saturated open-city variant, the Flip Schelling Process (FSP), in which agents, placed on a graph, have one out of two types and, based on the predominant type in their neighborhood, decide whether to change their types; similar to a new agent arriving as soon as another agent leaves the vertex. We investigate the probability that an edge {u,v} is monochrome, i.e., that both vertices u and v have the same type in the FSP, and we provide a general framework for analyzing the influence of the underlying graph topology on residential segregation. In particular, for two adjacent vertices, we show that a highly decisive common neighborhood, i.e., a common neighborhood where the absolute value of the difference between the number of vertices with different types is high, supports segregation and, moreover, that large common neighborhoods are more decisive. As an application, we study the expected behavior of the FSP on two common random graph models with and without geometry: (1) For random geometric graphs, we show that the existence of an edge {u,v} makes a highly decisive common neighborhood for u and v more likely. Based on this, we prove the existence of a constant c > 0 such that the expected fraction of monochrome edges after the FSP is at least 1/2 + c. (2) For Erdős-Rényi graphs we show that large common neighborhoods are unlikely and that the expected fraction of monochrome edges after the FSP is at most 1/2 + o(1). Our results indicate that the cluster structure of the underlying graph has a significant impact on the obtained segregation strength.
Cite as

Thomas Bläsius, Tobias Friedrich, Martin S. Krejca, and Louise Molitor. The Impact of Geometry on Monochrome Regions in the Flip Schelling Process. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.ISAAC.2021.29,
  author =	{Bl\"{a}sius, Thomas and Friedrich, Tobias and Krejca, Martin S. and Molitor, Louise},
  title =	{{The Impact of Geometry on Monochrome Regions in the Flip Schelling Process}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{29:1--29: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.29},
  URN =		{urn:nbn:de:0030-drops-154623},
  doi =		{10.4230/LIPIcs.ISAAC.2021.29},
  annote =	{Keywords: Agent-based Model, Schelling Segregation, Spin System}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.66
A Spectral Independence View on Hard Spheres via Block Dynamics

Authors: Tobias Friedrich, Andreas Göbel, Martin S. Krejca, and Marcus Pappik

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

Abstract
The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand-canonical partition function of the hard-sphere model in d dimensions. Up to a fugacity of λ < e/2^d, the runtime of our algorithm is polynomial in the volume of the system. This covers the entire known real-valued regime for the uniqueness of the Gibbs measure. Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization. To cope with the exponential blow-up of the discrete instance we use clique dynamics, a Markov chain that was recently introduced in the setting of abstract polymer models. We prove rapid mixing of clique dynamics up to the tree threshold of the univariate hard-core model. This is achieved by relating clique dynamics to block dynamics and adapting the spectral expansion method, which was recently used to bound the mixing time of Glauber dynamics within the same parameter regime.
Cite as

Tobias Friedrich, Andreas Göbel, Martin S. Krejca, and Marcus Pappik. A Spectral Independence View on Hard Spheres via Block Dynamics. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 66:1-66:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{friedrich_et_al:LIPIcs.ICALP.2021.66,
  author =	{Friedrich, Tobias and G\"{o}bel, Andreas and Krejca, Martin S. and Pappik, Marcus},
  title =	{{A Spectral Independence View on Hard Spheres via Block Dynamics}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{66:1--66:15},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.66},
  URN =		{urn:nbn:de:0030-drops-141353},
  doi =		{10.4230/LIPIcs.ICALP.2021.66},
  annote =	{Keywords: Hard-sphere Model, Markov Chain, Partition Function, Gibbs Distribution, Approximate Counting, Spectral Independence}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.6
Probabilistic Routing for On-Street Parking Search

Authors: Tobias Arndt, Danijar Hafner, Thomas Kellermeier, Simon Krogmann, Armin Razmjou, Martin S. Krejca, Ralf Rothenberger, and Tobias Friedrich

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

Abstract
An estimated 30% of urban traffic is caused by search for parking spots [Shoup, 2005]. Suggesting routes along highly probable parking spots could reduce traffic. In this paper, we formalize parking search as a probabilistic problem on a road graph and show that it is NP-complete. We explore heuristics that optimize for the driving duration and the walking distance to the destination. Routes are constrained to reach a certain probability threshold of finding a spot. Empirically estimated probabilities of successful parking attempts are provided by TomTom on a per-street basis. We release these probabilities as a dataset of about 80,000 roads covering the Berlin area. This allows to evaluate parking search algorithms on a real road network with realistic probabilities for the first time. However, for many other areas, parking probabilities are not openly available. Because they are effortful to collect, we propose an algorithm that relies on conventional road attributes only. Our experiments show that this algorithm comes close to the baseline by a factor of 1.3 in our cost measure. This leads to the conclusion that conventional road attributes may be sufficient to compute reasonably good parking search routes.
Cite as

Tobias Arndt, Danijar Hafner, Thomas Kellermeier, Simon Krogmann, Armin Razmjou, Martin S. Krejca, Ralf Rothenberger, and Tobias Friedrich. Probabilistic Routing for On-Street Parking Search. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{arndt_et_al:LIPIcs.ESA.2016.6,
  author =	{Arndt, Tobias and Hafner, Danijar and Kellermeier, Thomas and Krogmann, Simon and Razmjou, Armin and Krejca, Martin S. and Rothenberger, Ralf and Friedrich, Tobias},
  title =	{{Probabilistic Routing for On-Street Parking Search}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{6:1--6:13},
  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.6},
  URN =		{urn:nbn:de:0030-drops-63489},
  doi =		{10.4230/LIPIcs.ESA.2016.6},
  annote =	{Keywords: parking search, on-street parking, probabilistic routing, constrained optimization, dataset}
}
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