2 Search Results for "Jakob, Michal"

Document
DOI: 10.4230/LIPIcs.CCC.2019.24
Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs

Authors: Albert Atserias and Tuomas Hakoniemi

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)

Abstract
We show that if a system of degree-k polynomial constraints on n Boolean variables has a Sums-of-Squares (SOS) proof of unsatisfiability with at most s many monomials, then it also has one whose degree is of the order of the square root of n log s plus k. A similar statement holds for the more general Positivstellensatz (PS) proofs. This establishes size-degree trade-offs for SOS and PS that match their analogues for weaker proof systems such as Resolution, Polynomial Calculus, and the proof systems for the LP and SDP hierarchies of Lovász and Schrijver. As a corollary to this, and to the known degree lower bounds, we get optimal integrality gaps for exponential size SOS proofs for sparse random instances of the standard NP-hard constraint optimization problems. We also get exponential size SOS lower bounds for Tseitin and Knapsack formulas. The proof of our main result relies on a zero-gap duality theorem for pre-ordered vector spaces that admit an order unit, whose specialization to PS and SOS may be of independent interest.
Cite as

Albert Atserias and Tuomas Hakoniemi. Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{atserias_et_al:LIPIcs.CCC.2019.24,
  author =	{Atserias, Albert and Hakoniemi, Tuomas},
  title =	{{Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.24},
  URN =		{urn:nbn:de:0030-drops-108464},
  doi =		{10.4230/LIPIcs.CCC.2019.24},
  annote =	{Keywords: Proof complexity, semialgebraic proof systems, Sums-of-Squares, Positivstellensatz, trade-offs, lower bounds, monomial size, degree}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2015.16
Speedups for Multi-Criteria Urban Bicycle Routing

Authors: Jan Hrncir, Pavol Zilecky, Qing Song, and Michal Jakob

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)

Abstract
Increasing the adoption of cycling is crucial for achieving more sustainable urban mobility. Navigating larger cities on a bike is, however, often challenging due to cities’ fragmented cycling infrastructure and/or complex terrain topology. Cyclists would thus benefit from intelligent route planning that would help them discover routes that best suit their transport needs and preferences. Because of the many factors cyclists consider in deciding their routes, employing multi-criteria route search is vital for properly accounting for cyclists’ route-choice criteria. Direct application of optimal multi-criteria route search algorithms is, however, not feasible due to their prohibitive computational complexity. In this paper, we therefore propose several heuristics for speeding up multi-criteria route search. We evaluate our method on a real-world cycleway network and show that speedups of up to four orders of magnitude over the standard multi-criteria label-setting algorithm are possible with a reasonable loss of solution quality. Our results make it possible to practically deploy bicycle route planners capable of producing high-quality route suggestions respecting multiple real-world route-choice criteria.
Cite as

Jan Hrncir, Pavol Zilecky, Qing Song, and Michal Jakob. Speedups for Multi-Criteria Urban Bicycle Routing. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 16-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{hrncir_et_al:OASIcs.ATMOS.2015.16,
  author =	{Hrncir, Jan and Zilecky, Pavol and Song, Qing and Jakob, Michal},
  title =	{{Speedups for Multi-Criteria Urban Bicycle Routing}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{16--28},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.16},
  URN =		{urn:nbn:de:0030-drops-54584},
  doi =		{10.4230/OASIcs.ATMOS.2015.16},
  annote =	{Keywords: bicycle routing, multi-criteria shortest path, heuristic speedups}
}
  • Refine by Author
  • 1 Atserias, Albert
  • 1 Hakoniemi, Tuomas
  • 1 Hrncir, Jan
  • 1 Jakob, Michal
  • 1 Song, Qing
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Proof complexity

  • Refine by Keyword
  • 1 Positivstellensatz
  • 1 Proof complexity
  • 1 Sums-of-Squares
  • 1 bicycle routing
  • 1 degree
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2015
  • 1 2019

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