Piecewise linear valued constraint satisfaction problems with fixed number of variables
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Buch/Sammelband/Gutachten › Beigetragen › Begutachtung
Beitragende
Abstract
Many combinatorial optimisation problems can be modelled as valued constraint satisfaction problems. In this paper, we present a polynomial-time algorithm solving the valued constraint satisfaction problem for a fixed number of variables and for piecewise linear cost functions. Our algorithm finds the infimum of a piecewise linear function and decides whether it is a proper minimum.
Details
Originalsprache | Englisch |
---|---|
Titel | AIRO Springer Series |
Herausgeber (Verlag) | Springer International Publishing AG |
Seiten | 265-276 |
Seitenumfang | 12 |
Publikationsstatus | Veröffentlicht - 2021 |
Peer-Review-Status | Ja |
Externe IDs
ORCID | /0000-0001-8228-3611/work/142241061 |
---|
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- Fixed dimension, Infinite-domain optimisation, Linear programming, Piecewise linear cost functions, Valued constraint satisfaction