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
- Managementlehre und Operations Resarch - Fixed dimension, Infinite-domain optimisation, Linear programming, Piecewise linear cost functions, Valued constraint satisfaction
- Steuerung und Optimierung - Fixed dimension, Infinite-domain optimisation, Linear programming, Piecewise linear cost functions, Valued constraint satisfaction
- Angewandte Informatik - Fixed dimension, Infinite-domain optimisation, Linear programming, Piecewise linear cost functions, Valued constraint satisfaction
- Computational Mathematics - Fixed dimension, Infinite-domain optimisation, Linear programming, Piecewise linear cost functions, Valued constraint satisfaction
Schlagwörter
- Fixed dimension, Infinite-domain optimisation, Linear programming, Piecewise linear cost functions, Valued constraint satisfaction