Polynomial time approximation schemes for dense instances of minimum constraint satisfaction

DOI10.1002/rsa.10072zbMath1023.68093OpenAlexW2074844420MaRDI QIDQ4417004

Wenceslas Fernandez de la Vega, Cristina Bazgan, Marek Karpinski

Publication date: 6 August 2003

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10072

zbMATH Keywords

approximation algorithmsdense instancespolynomial time approximation schemesnearest codeword problemapproximation ratioshypergraph samplingminimum constraint satisfaction

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Related Items (1)

Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems

Cites Work

• Approximate max-flow min-(multi)cut theorems and their applications
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Polynomial time approximation schemes for dense instances of minimum constraint satisfaction