Integer Rounding for Polymatroid and Branching Optimization Problems
From MaRDI portal
Publication:3668310
DOI10.1137/0602044zbMath0518.90058OpenAlexW2032670317MaRDI QIDQ3668310
Shari R. Baum, Leslie E. jun. Trotter
Publication date: 1981
Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0602044
coveringbranchingintegral polymatroidsinteger round-down propertyinteger packingweak integral decomposition property
Integer programming (90C10) Combinatorial aspects of matroids and geometric lattices (05B35) Directed graphs (digraphs), tournaments (05C20) Polytopes and polyhedra (52Bxx)
Related Items
Families of non-IRUP instances of the one-dimensional cutting stock problem, An instance of the cutting stock problem for which the rounding property does not hold, Near-perfect matrices, A decomposition property of polyhedra, Integer round-up property for the chromatic number of some \(h\)-perfect graphs, On the chromatic index of multigraphs and a conjecture of Seymour (I), The cutting stock problem and integer rounding, A simple strategy for solving a class of 0-1 integer programming models, Non-interfering network flows, Error bounds for mixed integer nonlinear optimization problems, Fractional and integral colourings, Bin packing and related problems: general arc-flow formulation with graph compression, Unnamed Item, Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem, Parametric formulation of the general integer linear programming problem, A branch-and-price algorithm for capacitated hypergraph vertex separation, Testing additive integrality gaps, Constructing an instance of the cutting stock problem of minimum size which does not possess the integer round-up property, The modified integer round-up property of the one-dimensional cutting stock problem, Bounds for the Nakamura number, Notes on Equitable Partitions into Matching Forests in Mixed Graphs and into $b$-branchings in Digraphs, A feasible rounding approach for mixed-integer optimization problems, The \(b\)-branching problem in digraphs, Large proper gaps in bin packing and dual bin packing problems, Nested \((2,3)\)-instances of the cutting stock problem, A simple \(OPT+1\) algorithm for cutting stock under the modified integer round-up property assumption, Unnamed Item, Packing and covering with integral feasible flows in integral supply-demand networks, The proper relaxation and the proper gap of the skiving stock problem, Characterizing IRDP-instances of the skiving stock problem by means of polyhedral theory, Integer rounding and modified integer rounding for the skiving stock problem, Lower bounds and algorithms for the minimum cardinality bin covering problem, Membership criteria and containments of powers of monomial ideals, An upper bound of \(\Delta(E) < 3 \slash 2\) for skiving stock instances of the divisible case, A rounding theorem for unique binary tomographic reconstruction, Sensitive Instances of the Cutting Stock Problem, Tighter relaxations for the cutting stock problem, On some characterisations of totally unimodular matrices, Nearness and bound relationships between an integer-programming problem and its relaxed linear-programming problem, Approximation algorithms for scheduling unrelated parallel machines, Integral decomposition in polyhedra, An asymptotically exact algorithm for the high-multiplicity bin packing problem, Normality criteria for monomial ideals, Minimal proper non-IRUP instances of the one-dimensional cutting stock problem, Error bounds for mixed integer linear optimization problems
Cites Work
- Blocking pairs of polyhedra arising from network flows
- Blocking, antiblocking, and pairs of matroids and polymatroids
- Anti-blocking polyhedra
- Normal hypergraphs and the perfect graph conjecture
- Cyclic Scheduling via Integer Programs with Circular Ones
- Finite checkability for integer rounding properties in combinatorial programming problems
- Network Flows, Minimum Coverings, and the Four-Color Conjectures
- Unnetworks, with Applications to Idle Time Scheduling
- Transversals and matroid partition
- Minimum partition of a matroid into independent subsets
- Blocking and anti-blocking pairs of polyhedra
- Matroids and the greedy algorithm
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
