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

DOI10.1007/978-3-319-94667-2_31OpenAlexW4301785514MaRDI QIDQ1671024FDOQ1671024

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

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

zbMATH Keywords

orthogonal arraysoptimization constraint satisfaction problemsaverage differential ratio

Mathematics Subject Classification ID

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

Cited In (1)

• Constructions of optimal orthogonal arrays with repeated rows

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)