Approximation schemes for metric bisection and partitioning

zbMATH Open1317.68276MaRDI QIDQ5501299FDOQ5501299

Authors: W. Fernandez de la Vega, Marek Karpinski, Claire Kenyon 

Publication date: 3 August 2015

Recommendations

• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
• scientific article; zbMATH DE number 1688377
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• Approximation schemes for clustering problems
• A randomized approximation scheme for metric MAX-CUT

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (5)

• Optimal cuts and partitions in tree metrics in polynomial time
• The metric cutpoint partition problem
• Min sum clustering with penalties
• The metric bridge partition problem: Partitioning of a metric space into two subspaces linked by an edge in any optimal realization
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints

This page was built for publication: Approximation schemes for metric bisection and partitioning

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