A combinatorial algorithm for MAX CSP

DOI10.1016/S0020-0190(02)00435-0zbMath1173.68880OpenAlexW2084350425MaRDI QIDQ1007550

Mayur Datar, Rina Panigrahy, Rajeev Motwani, Tomás Feder, Aristides Gionis

Publication date: 23 March 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00435-0

zbMATH Keywords

combinatorial problemsanalysis of algorithmsdesign of algorithmsgraph algorithmsdatabasesalgorithmical approximation

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10)

Related Items (2)

Supermodular functions and the complexity of MAX CSP ⋮ Colouring, constraint satisfaction, and complexity

Uses Software

• MS SQL Server

Cites Work

• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p
• .879-approximation algorithms for MAX CUT and MAX 2SAT

This page was built for publication: A combinatorial algorithm for MAX CSP