×

Non-oblivious local search for MAX 2-CCSP with application to MAX DICUT. (English) Zbl 0890.68037

Möhring, Rolf H. (ed.), Graph-theoretic concepts in computer science. 23rd international workshop, WG ’97, Berlin, Germany, June 18–20, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1335, 2-14 (1997).
Summary: We give a fully dynamic \(5/2\)-approximate algorithm for the class of maximum binary conjunctive constraint satisfaction problem, and thus for the maximum directed cut problem. The proposed algorithm is based on the non-oblivious local search technique and on a neighborhood mapping that allows to change either one item, or all the items in the current solution. The total time required to maintain 5/2-approximate solutions, while an arbitrary sequence of \(q\) constraint insertions and deletions is performed, is \(O(m^2+ m\cdot q)\). This give \(O(m)\) amortized time per update over a sequence of \(\Omega(m)\) operations.
For the entire collection see [Zbl 0877.00011].

MSC:

68P10 Searching and sorting

Software:

CCSP
PDFBibTeX XMLCite