A local search algorithm for the constrained max cut problem on hypergraphs.
Preprint
- 18 December 2018
- preprint
- Published by PeerJ in PeerJ Preprints
Abstract
In the constrained max k-cut problem on hypergraphs, we are given a weighted hypergraph H=(V, E), an integer k and a set c of constraints. The goal is to divide the set V of vertices into k disjoint partitions in such a way that the sum of the weights of the hyperedges having at least two endpoints in different partitions is maximized and the partitions satisfy all the constraints in c. In this paper we present a local search algorithm for the constrained max k-cut problem on hypergraphs and show that it has approximation ratio 1-1/k for a variety of constraints c, such as for the constraints defining the max Steiner k-cut problem, the max multiway cut problem and the max k-cut problem. We also show that our local search algorithm can be used on the max k-cut problem with given sizes of parts and on the capacitated max k-cut problem, and has approximation ratio 1-|Vmax|/|V|, where |Vmax| is the cardinality of the biggest partition. In addition, we present a local search algorithm for the directed max k-cut problem that has approximation ratio (k-1)/(3k-2).Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- The capacitated max k-cut problemMathematical Programming, 2007
- The RPR2 rounding technique for semidefinite programsJournal of Algorithms, 2006
- Approximation algorithms for Max-3-Cut and other problems via complex semidefinite programmingJournal of Computer and System Sciences, 2004
- Approximate Local Search in Combinatorial OptimizationSIAM Journal on Computing, 2004
- A unified framework for obtaining improved approximation algorithms for maximum graph bisection problemsRandom Structures & Algorithms, 2002
- Approximation Algorithms for Maximization Problems Arising in Graph PartitioningJournal of Algorithms, 2001
- A 0.5-Approximation Algorithm for MAX DICUT with Given Sizes of PartsSIAM Journal on Discrete Mathematics, 2001
- Better approximation algorithms for Set Splitting and Not-All-Equal SatInformation Processing Letters, 1998
- Improved approximation algorithms for MAXk-CUT and MAX BISECTIONAlgorithmica, 1997
- How easy is local search?Journal of Computer and System Sciences, 1988