Simple Approximation Algorithms for MAXNAESP and Hypergraph 2-colorability

Daya Ram Gaur () and Ramesh Krishnamurti ()
Additional contact information
Daya Ram Gaur: Simon Fraser University
Ramesh Krishnamurti: Simon Fraser University

Journal of Combinatorial Optimization, 2001, vol. 5, issue 2, No 2, 167-173

Abstract: Abstract Hypergraph 2-colorability, also known as set splitting, is a widely studied problem in graph theory. In this paper we study the maximization version of the same. We recast the problem as a special type of satisfiability problem and give approximation algorithms for it. Our results are valid for hypergraph 2-colorability, set splitting and MAX-CUT (which is a special case of hypergraph 2-colorability) because the reductions are approximation preserving. Here we study the MAXNAESP problem, the optimal solution to which is a truth assignment of the literals that maximizes the number of clauses satisfied. As a main result of the paper, we show that any locally optimal solution (a solution is locally optimal if its value cannot be increased by complementing assignments to literals and pairs of literals) is guaranteed a performance ratio of $$\frac{1}{2} + \varepsilon$$ . This is an improvement over the ratio of $$\frac{1}{2}$$ attributed to another local improvement heuristic for MAX-CUT (C. Papadimitriou, Computational Complexity, Addison Wesley, 1994). In fact we provide a bound of $$\frac{k}{{k + 1}}$$ for this problem, where k ≥ 3 is the minimum number of literals in a clause. Such locally optimal algorithms appear to subsume typical greedy algorithms that have been suggested for problems in the general domain of satisfiability. It should be noted that the NAESP problem where each clause has exactly two literals, is equivalent to MAX-CUT. However, obtaining good approximation ratios using semi-definite programming techniques (M. Goemans and D.P. Williamson, in Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 1994a, pp. 422–431) appears difficult. Also, the randomized rounding algorithm as well as the simple randomized algorithm both (M. Goemans and D.P. Williamson, SIAM J. Disc. Math, vol. 7, pp. 656–666, 1994b) yield a bound of $$\frac{1}{2}$$ for the MAXNAESP problem. In contrast to this, the algorithm proposed in this paper obtains a bound of $$\frac{1}{2} + \varepsilon$$ for this problem.

Keywords: approximation algorithms; hypergraph 2-colorability; set splitting; MAXNAESP; MAX-CUT (search for similar items in EconPapers)
Date: 2001
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1011453115618 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:5:y:2001:i:2:d:10.1023_a:1011453115618

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1011453115618

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().