zbMATH — the first resource for mathematics

Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances. (English) Zbl 1279.68108
Arora, Sanjeev (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 6th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2003 and 7th international workshop on randomization and approximation techniques in computer science, RANDOM 2003, Princeton, NJ, USA, August 24–26, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40770-7/pbk). Lect. Notes Comput. Sci. 2764, 382-395 (2003).
Summary: We show that a random instance of a weighted maximum constraint satisfaction problem (or max 2-csp), whose clauses are over pairs of binary variables, is solvable by a deterministic algorithm in polynomial expected time, in the “sparse” regime where the expected number of clauses is half the number of variables. In particular, a maximum cut in a random graph with edge density \(1/n\) or less can be found in polynomial expected time.
Our method is to show, first, that if a max 2-csp has a connected underlying graph with \(n\) vertices and \(m\) edges, the solution time can be deterministically bounded by \(2^{(m-n)/2}\). Then, analyzing the tails of the distribution of this quantity for a component of a random graph yields our result. An alternative deterministic bound on the solution time, as \(2^{m/5}\), improves upon a series of recent results.
For the entire collection see [Zbl 1026.00023].

68Q25 Analysis of algorithms and problem complexity
05C85 Graph algorithms (graph-theoretic aspects)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI