A 0.5-Approximation Algorithm for MAX DICUT with Given Sizes of Parts

DOI10.1137/S089548010036813XzbMath0968.68198MaRDI QIDQ2719167

A. A. Ageev, M. I. Sviridenko, Refael Hassin

Publication date: 21 June 2001

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s089548010036813x

zbMATH Keywords

approximation algorithm; linear relaxation; directed cut; basic solution

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C27: Combinatorial optimization

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Constrained Assortment Optimization Under the Paired Combinatorial Logit Model, A maximum dicut in a digraph induced by a minimal dominating set, Improved approximation algorithms for maximum graph partitioning problems, The capacitated max \(k\)-cut problem, Approximating graph-constrained max-cut, Approximation algorithm for MAX DICUT with given sizes of parts, A new greedy strategy for maximizing monotone submodular function under a cardinality constraint, Maximizing a non-decreasing non-submodular function subject to various types of constraints, Approximating max-cut under graph-MSO constraints, The fundamental theorem of linear programming: extensions and applications, Max-Cut Under Graph Constraints, An approximation algorithm for maxk-uncut with capacity constraints