5 Search Results for "Mamino, Marcello"

Document
DOI: 10.4230/LIPIcs.MFCS.2025.24
Temporal Valued Constraint Satisfaction Problems

Authors: Manuel Bodirsky, Édouard Bonnet, and Žaneta Semanišinová

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We study the computational complexity of the valued constraint satisfaction problem (VCSP) for every valued structure over ℚ that is preserved by all order-preserving bijections. Such VCSPs will be called temporal, in analogy to the (classical) constraint satisfaction problem: a relational structure is preserved by all order-preserving bijections if and only if all its relations have a first-order definition in (ℚ; <), and the CSPs for such structures are called temporal CSPs. Many optimization problems that have been studied intensively in the literature can be phrased as a temporal VCSP. We prove that a temporal VCSP is in P, or NP-complete. Our analysis uses the concept of fractional polymorphisms. This is the first dichotomy result for VCSPs over infinite domains which is complete in the sense that it treats all valued structures that contain a given automorphism group.
Cite as

Manuel Bodirsky, Édouard Bonnet, and Žaneta Semanišinová. Temporal Valued Constraint Satisfaction Problems. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.MFCS.2025.24,
  author =	{Bodirsky, Manuel and Bonnet, \'{E}douard and Semani\v{s}inov\'{a}, \v{Z}aneta},
  title =	{{Temporal Valued Constraint Satisfaction Problems}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{24:1--24:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.24},
  URN =		{urn:nbn:de:0030-drops-241311},
  doi =		{10.4230/LIPIcs.MFCS.2025.24},
  annote =	{Keywords: Constraint Satisfaction Problems, valued CSPs, temporal CSPs, fractional polymorphisms, complexity dichotomy, min CSPs}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.145
Reducing Stochastic Games to Semidefinite Programming

Authors: Manuel Bodirsky, Georg Loho, and Mateusz Skomra

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We present a polynomial-time reduction from max-average constraints to the feasibility problem for semidefinite programs. This shows that Condon’s simple stochastic games, stochastic mean payoff games, and in particular mean payoff games and parity games can all be reduced to semidefinite programming.
Cite as

Manuel Bodirsky, Georg Loho, and Mateusz Skomra. Reducing Stochastic Games to Semidefinite Programming. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 145:1-145:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.ICALP.2025.145,
  author =	{Bodirsky, Manuel and Loho, Georg and Skomra, Mateusz},
  title =	{{Reducing Stochastic Games to Semidefinite Programming}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{145:1--145:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.145},
  URN =		{urn:nbn:de:0030-drops-235224},
  doi =		{10.4230/LIPIcs.ICALP.2025.145},
  annote =	{Keywords: Mean-payoff games, stochastic games, semidefinite programming, max-average constraints, max-atom problem}
}
Document
DOI: 10.4230/LIPIcs.CSL.2018.12
Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains

Authors: Manuel Bodirsky, Marcello Mamino, and Caterina Viola

Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)

Abstract
Valued constraint satisfaction problems (VCSPs) are a large class of combinatorial optimisation problems. It is desirable to classify the computational complexity of VCSPs depending on a fixed set of allowed cost functions in the input. Recently, the computational complexity of all VCSPs for finite sets of cost functions over finite domains has been classified in this sense. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain. We initiate the systematic investigation of infinite-domain VCSPs by studying the complexity of VCSPs for piecewise linear homogeneous cost functions. We remark that in this paper the infinite domain will always be the set of rational numbers. We show that such VCSPs can be solved in polynomial time when the cost functions are additionally submodular, and that this is indeed a maximally tractable class: adding any cost function that is not submodular leads to an NP-hard VCSP.
Cite as

Manuel Bodirsky, Marcello Mamino, and Caterina Viola. Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.CSL.2018.12,
  author =	{Bodirsky, Manuel and Mamino, Marcello and Viola, Caterina},
  title =	{{Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic (CSL 2018)},
  pages =	{12:1--12:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Ghica, Dan R. and Jung, Achim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.12},
  URN =		{urn:nbn:de:0030-drops-96792},
  doi =		{10.4230/LIPIcs.CSL.2018.12},
  annote =	{Keywords: Valued constraint satisfaction problems, Piecewise linear functions, Submodular functions, Semilinear, Constraint satisfaction, Optimisation, Model Theory}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.33
The Complexity of Disjunctive Linear Diophantine Constraints

Authors: Manuel Bodirsky, Barnaby Martin, Marcello Mamino, and Antoine Mottet

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We study the Constraint Satisfaction Problem CSP( A), where A is first-order definable in (Z;+,1) and contains +. We prove such problems are either in P or NP-complete.
Cite as

Manuel Bodirsky, Barnaby Martin, Marcello Mamino, and Antoine Mottet. The Complexity of Disjunctive Linear Diophantine Constraints. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.MFCS.2018.33,
  author =	{Bodirsky, Manuel and Martin, Barnaby and Mamino, Marcello and Mottet, Antoine},
  title =	{{The Complexity of Disjunctive Linear Diophantine Constraints}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul 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.MFCS.2018.33},
  URN =		{urn:nbn:de:0030-drops-96150},
  doi =		{10.4230/LIPIcs.MFCS.2018.33},
  annote =	{Keywords: Constraint Satisfaction, Presburger Arithmetic, Computational Complexity}
}
Document
DOI: 10.4230/DFU.Vol7.15301.79
Constraint Satisfaction Problems over Numeric Domains

Authors: Manuel Bodirsky and Marcello Mamino

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)

Abstract
We present a survey of complexity results for constraint satisfaction problems (CSPs) over the integers, the rationals, the reals, and the complex numbers. Examples of such problems are feasibility of linear programs, integer linear programming, the max-atoms problem, Hilbert's tenth problem, and many more. Our particular focus is to identify those CSPs that can be solved in polynomial time, and to distinguish them from CSPs that are NP-hard. A very helpful tool for obtaining complexity classifications in this context is the concept of a polymorphism from universal algebra.
Cite as

Manuel Bodirsky and Marcello Mamino. Constraint Satisfaction Problems over Numeric Domains. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 79-111, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InCollection{bodirsky_et_al:DFU.Vol7.15301.79,
  author =	{Bodirsky, Manuel and Mamino, Marcello},
  title =	{{Constraint Satisfaction Problems over Numeric Domains}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{79--111},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.79},
  URN =		{urn:nbn:de:0030-drops-69580},
  doi =		{10.4230/DFU.Vol7.15301.79},
  annote =	{Keywords: Constraint satisfaction problems, Numerical domains}
}
  • Refine by Type
  • 5 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 2 2018
  • 1 2017

  • Refine by Author
  • 5 Bodirsky, Manuel
  • 3 Mamino, Marcello
  • 1 Bonnet, Édouard
  • 1 Loho, Georg
  • 1 Martin, Barnaby
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs
  • 1 DFU

  • Refine by Classification
  • 3 Theory of computation → Complexity theory and logic
  • 1 Mathematics of computing → Mathematical optimization
  • 1 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Problems, reductions and completeness
  • 1 Theory of computation → Semidefinite programming

  • Refine by Keyword
  • 1 Computational Complexity
  • 1 Constraint Satisfaction
  • 1 Constraint Satisfaction Problems
  • 1 Constraint satisfaction
  • 1 Constraint satisfaction problems
  • 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