A Polynomial Time Algorithm for Shaped Partition Problems

DOI10.1137/S1052623497344002zbMath0955.90118OpenAlexW2016814046MaRDI QIDQ4702337

Shmuel Onn, Uriel G. Rothblum, Frank K. Hwang

Publication date: 24 November 1999

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s1052623497344002

zbMATH Keywords

clusteroptimizationenumerationpolytopeconvexseparationpolynomial timeshaped partition problems

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (26)

Counting disjoint 2-partitions for points in the plane ⋮ The complexity of vector partition ⋮ The mean-partition problem ⋮ Screening multi‐dimensional heterogeneous populations for infectious diseases under scarce testing resources, with application to <scp>COVID</scp>‐19 ⋮ An LP-based \(k\)-means algorithm for balancing weighted point sets ⋮ The Hilbert zonotope and a polynomial time algorithm for universal Gröbner bases. ⋮ An exact algorithm for finding a vector subset with the longest sum ⋮ Nonlinear bipartite matching ⋮ Convex integer optimization by constantly many linear counterparts ⋮ On the number of separable partitions ⋮ The use of edge-directions and linear programming to enumerate vertices ⋮ The partition bargaining problem ⋮ Efficient solutions for weight-balanced partitioning problems ⋮ Sphere-separable partitions of multi-parameter elements ⋮ Are there more almost separable partitions than separable partitions? ⋮ Complexity and approximation of finding the longest vector sum ⋮ Cutting corners ⋮ Circuits in extended formulations ⋮ Complexity and algorithms for finding a subset of vectors with the longest sum ⋮ Easy NP-hardness Proofs of Some Subset Choice Problems ⋮ Convex integer maximization via Graver bases ⋮ Approximability of the Problem of Finding a Vector Subset with the Longest Sum ⋮ Separable partitions ⋮ Linear-shaped partition problems ⋮ Vertex characterization of partition polytopes of bipartitions and of planar point sets ⋮ On the number of corner cuts

This page was built for publication: A Polynomial Time Algorithm for Shaped Partition Problems