Piecewise linear valued constraint satisfaction problems with fixed number of variables
Research output: Contribution to book/Conference proceedings/Anthology/Report › Chapter in book/Anthology/Report › Contributed › peer-review
Contributors
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
| Original language | English |
|---|---|
| Title of host publication | AIRO Springer Series |
| Publisher | Springer International Publishing AG |
| Pages | 265-276 |
| Number of pages | 12 |
| Publication status | Published - 2021 |
| Peer-reviewed | Yes |
External IDs
| ORCID | /0000-0001-8228-3611/work/142241061 |
|---|
Keywords
ASJC Scopus subject areas
Keywords
- Fixed dimension, Infinite-domain optimisation, Linear programming, Piecewise linear cost functions, Valued constraint satisfaction