An integer analogue of Carathéodory's theorem

DOI10.1016/0095-8956(86)90064-XzbMath0589.52005DBLPjournals/jct/CookFS86WikidataQ29036469 ScholiaQ29036469MaRDI QIDQ1074117

Jean Fonlupt, William Cook

Publication date: 1986

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

zbMATH Keywords

integer programminggraph theorymatroid theoryrational coneCarathéodory's theorem for convex cones

Mathematics Subject Classification ID

Integer programming (90C10) Inequalities and extremum problems involving convexity in convex geometry (52A40) Combinatorial aspects of matroids and geometric lattices (05B35) Polytopes and polyhedra (52Bxx)

Related Items (29)

About the Complexity of Two-Stage Stochastic IPs ⋮ Quantum jumps of normal polytopes ⋮ Stronger bounds and faster algorithms for packing in generalized kernel systems ⋮ A Discrete Convex Min-Max Formula for Box-TDI Polyhedra ⋮ The Support of Integer Optimal Solutions ⋮ Normal polytopes: between discrete, continuous, and random ⋮ Convex normality of rational polytopes with long edges ⋮ Improved bound for the Carathéodory rank of the bases of a matroid ⋮ New Bounds for the Integer Carathéodory Rank ⋮ \(n\)-fold integer programming in cubic time ⋮ Alternatives for testing total dual integrality ⋮ The Distributions of Functions Related to Parametric Integer Optimization ⋮ Packing and covering with integral feasible flows in integral supply-demand networks ⋮ Near-Linear Time Algorithm for $n$-Fold ILPs via Color Coding ⋮ Distance-Sparsity Transference for Vertices of Corner Polyhedra ⋮ Faster Algorithms for Integer Programs with Block Structure ⋮ A faster algorithm for packing branchings in digraphs ⋮ Combinatorial properties of integer matrices and integer matrices modk ⋮ Normal polytopes and ellipsoids ⋮ Alternating sign matrices, extensions and related cones ⋮ Carathéodory bounds for integer cones ⋮ Sparse Solutions of Linear Diophantine Equations ⋮ Non-standard approaches to integer programming ⋮ The combinatorics of modeling and analyzing biological systems ⋮ Graphs with the Circuit Cover Property ⋮ Unnamed Item ⋮ Polyhedra with the integer Carathéodory property ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Test sets of integer programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Total dual integrality and integer polyhedra
• On the integrality of an extreme solution to pluperfect graph and balanced systems
• Testing membership in matroid polyhedra
• On total dual integrality
• Normal hypergraphs and the perfect graph conjecture
• Proving total dual integrality with cross-free families—A general framework
• A generalization of max flow—min cut
• Some Basis Theorems for Integral Monoids
• Minimum partition of a matroid into independent subsets

This page was built for publication: An integer analogue of Carathéodory's theorem