Randomized approximation of the constraint satisfaction problem

DOI10.1007/3-540-61422-2_122zbMATH Open0889.90116OpenAlexW2043541258MaRDI QIDQ4375640FDOQ4375640

Osamu Watanabe, Hoong Chuin Lau

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

Recommendations

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

zbMATH Keywords

randomized roundingmethod of conditional probabilities

Mathematics Subject Classification ID

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

Cited In (17)

• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Models for Random Constraint Satisfaction Problems
• A new approach for weighted constraint satisfaction
• Branch-and-bound solves random binary IPs in poly\((n)\)-time
• Approximations and randomization to boost CSP techniques
• Title not available (Why is that?)
• Performances of pure random walk algorithms on constraint satisfaction problems with growing domains
• Practically uniform solution sampling in constraint programming
• Random constraint satisfaction: Flaws and structure
• Title not available (Why is that?)
• On the advantage over a random assignment
• Randomized Post-optimization for t-Restrictions
• An average analysis of backtracking on random constraint satisfaction problems
• On the freezing of variables in random constraint satisfaction problems
• Title not available (Why is that?)
• Backtracking and random 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)