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

DOI10.1137/S089548010036813XzbMath0968.68198OpenAlexW2046506015MaRDI 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 algorithmlinear relaxationdirected cutbasic solution

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (12)

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

This page was built for publication: A 0.5-Approximation Algorithm for MAX DICUT with Given Sizes of Parts