Piecewise Linear Valued Constraint Satisfaction Problems with Fixed Number of Variables

2020/03/02 by Manuel Bodirsky, Bodirsky, Manuel, Marcello Mamino +3
Computer Science · Engineering · #90 #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO) #Optimization and Control (math.OC) #Optimization and Packing Problems

paper · pdf · doi:10.48550/arxiv.2003.00963

openalex publication_date 2020/03/02 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28

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.

Related

• Submodular Functions and Valued Constraint Satisfaction Problems over\n Infinite Domains
• The power of linear programming for valued CSPs: a constructive characterization
• A polynomial-time algorithm for median-closed semilinear constraints
• A Reduction from Valued CSP to Min Cost Homomorphism Problem for Digraphs
• Min CSP on Four Elements: Moving Beyond Submodularity