Some efficiently solvable problems over integer partition polytopes

DOI10.1016/J.DAM.2014.08.015MaRDI QIDQ476314zbMATH OpenOpenAlexFDO

Authors Shmuel Onn, Vladimir A. Shlyk

Publication date 28 November 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2014.08.015

zbMATH Keywords

integer partitionsinteger partition polytopeseparation problemvertex adjacency

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Partitions; congruences and congruential restrictions (11P83)

Recommendations

• Polytopes of partitions of numbers
• Projection results for the \(k\)-partition problem
• Vertex characterization of partition polytopes of bipartitions and of planar point sets
• The partition problem
• Primal separation algorithms

Cites work

• scientific article; zbMATH DE number 3121293 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 3577263 (Why is no real title available?)
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Enumerative combinatorics. Volume 2.
• Geometric algorithms and combinatorial optimization.
• Large sparse numerical optimization
• Optimal integer partitions
• Polyhedral Characterization of Discrete Dynamic Programming
• Polyhedral approach to integer partitions
• Polyhedral proof methods in combinatorial optimization
• Polytopes of partitions of numbers

Cited in

(13)

• A formulation of the wide partition conjecture using the atom problem in discrete tomography
• scientific article; zbMATH DE number 808805 (Why is no real title available?)
• On the complexity of Hilbert refutations for partition
• scientific article; zbMATH DE number 1985302 (Why is no real title available?)
• EXACT SOLUTIONS OF RECTANGULAR PARTITIONS VIA INTEGER PROGRAMMING
• Optimal Dorfman group testing for symmetric distributions
• Combinatorial operations for the generation of vertices of integer partition polytopes
• Extension complexity of formal languages
• Well-solvable instances for the partition problem
• Feasible partition problem in reverse convex and convex mixed-integer programming
• Application of regular partitions in integer programming
• Rectangular partition is polynomial in two dimensions but NP-complete in three
• Number of Vertices of the Polytope of Integer Partitions and Factorization of the Partitioned Number

This page was built for publication: Some efficiently solvable problems over integer partition polytopes

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