How far from a worst solution a random solution of a k CSP instance can be?

DOI10.1007/978-3-319-94667-2_31MaRDI QIDQ1671024zbMATH OpenOpenAlexFDO

Authors Jean-François Culus, Sophie Toulouse

Publication date 6 September 2018

Full work available at URL https://doi.org/10.1007/978-3-319-94667-2_31

zbMATH Keywords

average differential ratiooptimization constraint satisfaction problemsorthogonal arrays

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Recommendations

• On the constraint length of random \(k\)-CSP
• Randomized approximation of the constraint satisfaction problem
• On the solution-space geometry of random constraint satisfaction problems
• An upper (lower) bound for Max (Min) CSP
• Random constraint satisfaction: A more accurate picture

Cited in

(9)

• Constructions of optimal orthogonal arrays with repeated rows
• The construction of optimal orthogonal arrays with repeated rows and strength 2
• New results on optimal 2-level orthogonal arrays with repeated rows
• Construction of high strength orthogonal arrays with repeated rows
• Constructions of optimal 2-level orthogonal arrays with repeated rows
• From worst case to the average: structural guarantees in k-CSP approximation via orthogonal arrays
• Construction of asymmetric orthogonal arrays with repeated rows
• Bounds and constructions of optimal orthogonal arrays with repeated rows
• Optimizing alphabet reduction pairs of arrays

This page was built for publication: How far from a worst solution a random solution of a \(k\) CSP instance can be?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1671024)