2 Search Results for "Feller, Thomas"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.47
Time Lower Bounds for the Metropolis Process and Simulated Annealing

Authors: Zongchen Chen, Dan Mikulincer, Daniel Reichman, and Alexander S. Wein

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

Abstract
The Metropolis process (MP) and Simulated Annealing (SA) are stochastic local search heuristics that are often used in solving combinatorial optimization problems. Despite significant interest, there are very few theoretical results regarding the quality of approximation obtained by MP and SA (with polynomially many iterations) for NP-hard optimization problems. We provide rigorous lower bounds for MP and SA with respect to the classical maximum independent set problem when the algorithms are initialized from the empty set. We establish the existence of a family of graphs for which both MP and SA fail to find approximate solutions in polynomial time. More specifically, we show that for any ε ∈ (0,1) there are n-vertex graphs for which the probability SA (when limited to polynomially many iterations) will approximate the optimal solution within ratio Ω(1/n^{1-ε}) is exponentially small. Our lower bounds extend to graphs of constant average degree d, illustrating the failure of MP to achieve an approximation ratio of Ω(log(d)/d) in polynomial time. In some cases, our lower bounds apply even when the temperature is chosen adaptively. Finally, we prove exponential-time lower bounds when the inputs to these algorithms are bipartite graphs, and even trees, which are known to admit polynomial-time algorithms for the independent set problem.
Cite as

Zongchen Chen, Dan Mikulincer, Daniel Reichman, and Alexander S. Wein. Time Lower Bounds for the Metropolis Process and Simulated Annealing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2025.47,
  author =	{Chen, Zongchen and Mikulincer, Dan and Reichman, Daniel and Wein, Alexander S.},
  title =	{{Time Lower Bounds for the Metropolis Process and Simulated Annealing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{47:1--47:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.47},
  URN =		{urn:nbn:de:0030-drops-244138},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.47},
  annote =	{Keywords: Metropolis Process, Simulated Annealing, Independent Set}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2023.18
Finite-Cliquewidth Sets of Existential Rules: Toward a General Criterion for Decidable yet Highly Expressive Querying

Authors: Thomas Feller, Tim S. Lyon, Piotr Ostropolski-Nalewaja, and Sebastian Rudolph

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract
In our pursuit of generic criteria for decidable ontology-based querying, we introduce finite-cliquewidth sets (fcs) of existential rules, a model-theoretically defined class of rule sets, inspired by the cliquewidth measure from graph theory. By a generic argument, we show that fcs ensures decidability of entailment for a sizable class of queries (dubbed DaMSOQs) subsuming conjunctive queries (CQs). The fcs class properly generalizes the class of finite-expansion sets (fes), and for signatures of arity ≤ 2, the class of bounded-treewidth sets (bts). For higher arities, bts is only indirectly subsumed by fcs by means of reification. Despite the generality of fcs, we provide a rule set with decidable CQ entailment (by virtue of first-order-rewritability) that falls outside fcs, thus demonstrating the incomparability of fcs and the class of finite-unification sets (fus). In spite of this, we show that if we restrict ourselves to single-headed rule sets over signatures of arity ≤ 2, then fcs subsumes fus.
Cite as

Thomas Feller, Tim S. Lyon, Piotr Ostropolski-Nalewaja, and Sebastian Rudolph. Finite-Cliquewidth Sets of Existential Rules: Toward a General Criterion for Decidable yet Highly Expressive Querying. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{feller_et_al:LIPIcs.ICDT.2023.18,
  author =	{Feller, Thomas and Lyon, Tim S. and Ostropolski-Nalewaja, Piotr and Rudolph, Sebastian},
  title =	{{Finite-Cliquewidth Sets of Existential Rules: Toward a General Criterion for Decidable yet Highly Expressive Querying}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.18},
  URN =		{urn:nbn:de:0030-drops-177602},
  doi =		{10.4230/LIPIcs.ICDT.2023.18},
  annote =	{Keywords: existential rules, TGDs, cliquewidth, treewidth, bounded-treewidth sets, finite-unification sets, first-order rewritability, monadic second-order logic, datalog}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2023

  • Refine by Author
  • 1 Chen, Zongchen
  • 1 Feller, Thomas
  • 1 Lyon, Tim S.
  • 1 Mikulincer, Dan
  • 1 Ostropolski-Nalewaja, Piotr
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Database query languages (principles)
  • 1 Theory of computation → Description logics
  • 1 Theory of computation → Logic and databases

  • Refine by Keyword
  • 1 Independent Set
  • 1 Metropolis Process
  • 1 Simulated Annealing
  • 1 TGDs
  • 1 bounded-treewidth sets
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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