A Polynomial Time Algorithm for Shaped Partition Problems

DOI10.1137/S1052623497344002MaRDI QIDQ4702337zbMATH OpenOpenAlexFDO

Authors 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

clusterconvexenumerationoptimizationpolynomial timepolytopeseparationshaped partition problems

Mathematics Subject Classification ID

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

Recommendations

• The vector partition problem for convex objective functions.
• Vertex characterization of partition polytopes of bipartitions and of planar point sets
• An adaptive algorithm for vector partitioning
• Representations and characterizations of vertices of bounded-shape partition polytopes

Cited in

(30)

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

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

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