Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
From MaRDI portal
Publication:2775885
DOI10.1006/jagm.2001.1183zbMath1017.68086OpenAlexW2034543148MaRDI QIDQ2775885
Publication date: 8 July 2002
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/176bf9a99f8373fea8dd15a5cc1a99d20bf951b3
Semidefinite programming (90C22) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Related Items (46)
Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix ⋮ Approximation algorithm for MAX DICUT with given sizes of parts ⋮ Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster ⋮ Graph bisection revisited ⋮ Finding connected \(k\)-subgraphs with high density ⋮ On semidefinite programming relaxations of maximum \(k\)-section ⋮ Solving \(k\)-cluster problems to optimality with semidefinite programming ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ Finding Connected Dense $$k$$-Subgraphs ⋮ An approximation algorithm for maxk-uncut with capacity constraints ⋮ Super-polynomial approximation branching algorithms ⋮ A parameterized approximation scheme for generalized partial vertex cover ⋮ The densest \(k\)-subgraph problem on clique graphs ⋮ Matroid-constrained vertex cover ⋮ An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem ⋮ Online maximum \(k\)-coverage ⋮ Maximizing coverage while ensuring fairness: a tale of conflicting objectives ⋮ A dynamic edge covering and scheduling problem: complexity results and approximation algorithms ⋮ The capacitated max \(k\)-cut problem ⋮ Distributed discovery of large near-cliques ⋮ Approximation algorithms for maximum cut with limited unbalance ⋮ Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} ⋮ Approximating \(k\)-generalized connectivity via collapsing HSTs ⋮ Approximating the 2-catalog segmentation problem using semidefinite programming relaxations ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ Approximation algorithms for MAX RES CUT with limited unbalanced constraints ⋮ An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance ⋮ Optimization of product category allocation in multiple warehouses to minimize splitting of online supermarket customer orders ⋮ Approximating \(k\)-forest with resource augmentation: a primal-dual approach ⋮ An approximation algorithm for the partial vertex cover problem in hypergraphs ⋮ Relaxations of Combinatorial Problems Via Association Schemes ⋮ Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem ⋮ \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel ⋮ Finding a Dense-Core in Jellyfish Graphs ⋮ A randomised approximation algorithm for the hitting set problem ⋮ Online Maximum k-Coverage ⋮ Parameterized complexity of multi-node hubs ⋮ On approximation of max-vertex-cover ⋮ On solving the densestk-subgraph problem on large graphs ⋮ Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization ⋮ Moderately exponential time and fixed parameter approximation algorithms ⋮ Improved approximation algorithms for maximum graph partitioning problems ⋮ PTAS for densest \(k\)-subgraph in interval graphs ⋮ Randomized approximation for the set multicover problem in hypergraphs
This page was built for publication: Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
