Carathéodory bounds for integer cones
From MaRDI portal
Publication:2480055
DOI10.1016/j.orl.2005.09.008zbMath1152.90662OpenAlexW2026405784WikidataQ29306332 ScholiaQ29306332MaRDI QIDQ2480055
Friedrich Eisenbrand, Gennady Shmonin
Publication date: 28 March 2008
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: http://infoscience.epfl.ch/record/121640
Related Items
Two-Variable Logic with Counting and Trees, New Algorithmic Results for Bin Packing and Scheduling, Optimizing Sparsity over Lattices and Semigroups, On the complexity of timed pattern matching, Algorithms for multiprocessor scheduling with two job lengths and allocation restrictions, The syllogistic with unity, Huge Unimodular $n$-Fold Programs, Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory, The two‐variable fragment with counting and equivalence, NP satisfiability for arrays as powers, Small substructures and decidability issues for first-order logic with two variables, Approximation and online algorithms for multidimensional bin packing: a survey, On the bin packing problem with a fixed number of object weights, The Support of Integer Optimal Solutions, Reasoning with Global Assumptions in Arithmetic Modal Logics, Cardinality constraints for arrays (decidability results and applications), An Efficient PTAS for Parallel Machine Scheduling with Capacity Constraints, New Bounds for the Integer Carathéodory Rank, Generalized flatness constants, spanning lattice polytopes, and the Gromov width, Presburger Büchi tree automata with applications to logics with expressive counting, Linear Arithmetic with Stars, A simple \(OPT+1\) algorithm for cutting stock under the modified integer round-up property assumption, On algebraic array theories, Combinatorial \(n\)-fold integer programming and applications, The Distributions of Functions Related to Parametric Integer Optimization, Branching in branch-and-price: A generic scheme, Fractional Collections with Cardinality Bounds, and Mixed Linear Arithmetic with Stars, On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics, Distance-Sparsity Transference for Vertices of Corner Polyhedra, Closure properties of knapsack semilinear groups, Sparse Solutions of Linear Diophantine Equations, Approximating vector scheduling: almost matching upper and lower bounds, Decision Procedures for Multisets with Cardinality Constraints, An EPTAS for scheduling on unrelated machines of few different types, Counting Constraints in Flat Array Fragments, Closing the Gap for Makespan Scheduling via Sparsification Techniques, About the Structure of the Integer Cone and Its Application to Bin Packing, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Huge multiway table problems, Sparse representation of vectors in lattices and semigroups, New approximability results for two-dimensional bin packing
Cites Work
- Unnamed Item
- The vertices of the knapsack polytope
- An integer analogue of Carathéodory's theorem
- An instance of the cutting stock problem for which the rounding property does not hold
- A Polynomial Algorithm for Multiprocessor Scheduling with Two Job Lengths
- A Linear Programming Approach to the Cutting-Stock Problem
- A counterexample to an integer analogue of Carathéodory's theorem
