Approximation algorithms for maximization problems arising in graph partitioning

Recommendations

FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
Improved approximation algorithms for maximum graph partitioning problems
Approximation Algorithms for Some Graph Partitioning Problems
Approximation algorithms for maximally balanced connected graph partition
Approximation algorithms for maximally balanced connected graph partition
A class of bounded approximation algorithms for graph partitioning
On the sum-max graph partitioning problem
Approximating the Maximally Balanced Connected Partition Problem in graphs
scientific article; zbMATH DE number 4011955
Approximation techniques for hypergraph partitioning problems

Cited in

(62)

Solving \(k\)-cluster problems to optimality with semidefinite programming
An approximation algorithm for max k-uncut with capacity constraints
Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem
Finding connected \(k\)-subgraphs with high density
PTAS for densest \(k\)-subgraph in interval graphs
Randomized approximation for the set multicover problem in hypergraphs
A parameterized approximation scheme for generalized partial vertex cover
Relaxations of combinatorial problems via association schemes
Graph bisection revisited
Matroid-constrained vertex cover
FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
A dynamic edge covering and scheduling problem: complexity results and approximation algorithms
Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
A randomised approximation algorithm for the hitting set problem
Approximation algorithms for MAX RES CUT with limited unbalanced constraints
Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
Improved approximation algorithms for maximum graph partitioning problems
Approximation algorithm for MAX DICUT with given sizes of parts
An approximation algorithm for the partial vertex cover problem in hypergraphs
Improved linearized models for graph partitioning problem under capacity constraints
Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
On approximation of max-vertex-cover
An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
A note on robust subsets of transversal matroids
Online maximum \(k\)-coverage
Online maximum \(k\)-coverage
Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix
Optimization of product category allocation in multiple warehouses to minimize splitting of online supermarket customer orders
Finding Connected Dense k-Subgraphs
Super-polynomial approximation branching algorithms
Approximating max k-uncut via LP-rounding plus greed, with applications to densest k-subgraph
Finding a Dense-Core in Jellyfish Graphs
Planted models for the densest k-subgraph problem
The densest \(k\)-subgraph problem on clique graphs
Tight approximation algorithms for maximum separable assignment problems
Approximating \(k\)-forest with resource augmentation: a primal-dual approach
Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph
\((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel
Computational results of a semidefinite branch-and-bound algorithm for k-cluster
scientific article; zbMATH DE number 4076980 (Why is no real title available?)
Approximation algorithms for maximum cut with limited unbalance
On semidefinite programming relaxations of maximum \(k\)-section
scientific article; zbMATH DE number 1304324 (Why is no real title available?)
Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}
Minimization and parameterized variants of vertex partition problems on graphs
Approximating \(k\)-generalized connectivity via collapsing HSTs
An efficient semidefinite programming relaxation for the graph partition problem
Sum-of-squares lower bounds for densest k-subgraph
On solving the densest \(k\)-subgraph problem on large graphs
Approximating the 2-catalog segmentation problem using semidefinite programming relaxations
Approximation algorithms for maximally balanced connected graph partition
Distributed discovery of large near-cliques
Improved FPT approximation scheme and approximate kernel for biclique-free max k-weight SAT: greedy strikes back
Optirefine: densest subgraphs and maximum cuts with k refinements
On approximability of optimization problems related to red/blue-split graphs
scientific article; zbMATH DE number 3983202 (Why is no real title available?)
Maximizing coverage while ensuring fairness: a tale of conflicting objectives
The capacitated max \(k\)-cut problem
Moderately exponential time and fixed parameter approximation algorithms
Parameterized complexity of multi-node hubs

This page was built for publication: Approximation algorithms for maximization problems arising in graph partitioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2775885)