Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory

DOI10.1016/j.jcss.2016.07.004zbMath1349.90116arXiv1511.03403OpenAlexW2963673510MaRDI QIDQ314827

Shmuel Onn

Publication date: 16 September 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.03403

zbMATH Keywords

integer programmingbin packingmulticommodity flowcutting stockfixed-parameter tractableinteger Carathéodorymultiway tabletotally unimodular matrixtotally unimodular monoid

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Transportation, logistics and supply chain management (90B06)

Related Items

The Support of Integer Optimal Solutions, High-multiplicity \(N\)-fold IP via configuration LP

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• The Graver complexity of integer programming
• \(N\)-fold integer programming
• Nonlinear discrete optimization. An algorithmic theory
• Geometric algorithms and combinatorial optimization.
• \(n\)-fold integer programming in cubic time
• A lower bound for the Graver complexity of the incidence matrix of a complete bipartite graph
• Three centuries of categorical data analysis: Log-linear models and maximum likelihood estima\-tion
• Carathéodory bounds for integer cones
• A Polynomial Algorithm for Multiprocessor Scheduling with Two Job Lengths
• A Linear Programming Approach to the Cutting-Stock Problem
• Huge Unimodular $n$-Fold Programs
• The Complexity of Three-Way Statistical Tables
• Polynomiality for Bin Packing with a Constant Number of Item Types
• All Linear and Integer Programs Are Slim 3‐Way Transportation Programs