Randomized approximation of the constraint satisfaction problem

DOI10.1007/3-540-61422-2_122MaRDI QIDQ4375640zbMATH OpenOpenAlexFDO

Authors Hoong Chuin Lau, Osamu Watanabe

Publication date 22 June 1998

Published in Algorithm Theory — SWAT'96 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61422-2_122

zbMATH Keywords

method of conditional probabilitiesrandomized rounding

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10)

Recommendations

• scientific article; zbMATH DE number 1002207
• scientific article; zbMATH DE number 1303558
• scientific article; zbMATH DE number 6381632
• A new approach for weighted constraint satisfaction

Cited in

(19)

• Backtracking and random constraint satisfaction
• How far from a worst solution a random solution of a \(k\) CSP instance can be?
• Approximations and randomization to boost CSP techniques
• Practically uniform solution sampling in constraint programming
• An average analysis of backtracking on random constraint satisfaction problems
• On the freezing of variables in random constraint satisfaction problems
• scientific article; zbMATH DE number 1002207 (Why is no real title available?)
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Performances of pure random walk algorithms on constraint satisfaction problems with growing domains
• scientific article; zbMATH DE number 5547880 (Why is no real title available?)
• Models for Random Constraint Satisfaction Problems
• Randomized Post-optimization for t-Restrictions
• scientific article; zbMATH DE number 1420826 (Why is no real title available?)
• scientific article; zbMATH DE number 7301529 (Why is no real title available?)
• On the advantage over a random assignment
• Random constraint satisfaction: Flaws and structure
• Branch-and-bound solves random binary IPs in poly(n)-time
• A new approach for weighted constraint satisfaction
• Spines of random constraint satisfaction problems: definition and connection with computational complexity

This page was built for publication: Randomized approximation of the constraint satisfaction problem

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