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

(63)

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

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)