Approximability of maximum splitting of k-sets and some other Apx-complete problems

DOI10.1016/0020-0190(96)00046-4zbMath0998.90525OpenAlexW2026634792WikidataQ127007645 ScholiaQ127007645MaRDI QIDQ1350605

Jens Lagergren, Alessandro Panconesi, Viggo Kann

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(96)00046-4

zbMATH Keywords

AlgorithmsComputational complexityApproximationCombinatorial problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Related Items (9)

Improved approximations for max set splitting and max NAE SAT ⋮ Orienting graphs to optimize reachability ⋮ Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat} ⋮ Approximation with a fixed number of solutions of some multiobjective maximization problems ⋮ On the hardness of efficiently approximating maximal non-\(L\) submatrices. ⋮ An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance ⋮ Improved parameterized set splitting algorithms: A Probabilistic approach ⋮ On weighted vs unweighted versions of combinatorial optimization problems ⋮ Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.

Cites Work

• Optimization, approximation, and complexity classes
• Approximation algorithms for combinatorial problems
• The hardness of approximation: Gap location
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• A Greedy Heuristic for the Set-Covering Problem
• On the hardness of approximating minimization problems
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximability of maximum splitting of k-sets and some other Apx-complete problems