On Integer Programming and Convolution.

DOI10.4230/LIPIcs.ITCS.2019.43zbMath1502.68138OpenAlexW2964238278MaRDI QIDQ5090420

Lars Rohwedder, Klaus Jansen

Publication date: 18 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/10136/pdf/LIPIcs-ITCS-2019-43.pdf/

zbMATH Keywords

integer programmingdynamic programmingconvolutionSETH

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Integer programming (90C10) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (16)

On lattice point counting in \(\varDelta\)-modular polyhedra ⋮ Improving the Cook et al. proximity bound given integral valued constraints ⋮ A note on a variant of the online open end bin packing problem ⋮ A note on coloring \((4K_1, C_4, C_6)\)-free graphs with a \(C_7\) ⋮ High-multiplicity \(N\)-fold IP via configuration LP ⋮ From approximate to exact integer programming ⋮ Optimizing low dimensional functions over the integers ⋮ A colorful Steinitz lemma with application to block-structured integer programs ⋮ On the optimality of pseudo-polynomial algorithms for integer programming ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ The Distributions of Functions Related to Parametric Integer Optimization ⋮ Unnamed Item ⋮ Local linear set on graphs with bounded twin cover number

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Necklaces, convolutions, and \(X+Y\)
• Clustered Integer 3SUM via Additive Combinatorics
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• On the complexity of integer programming
• A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
• Better Approximations for Tree Sparsity in Nearly-Linear Time
• On the Optimality of Pseudo-polynomial Algorithms for Integer Programming
• On Problems Equivalent to (min,+)-Convolution
• SETH-Based Lower Bounds for Subset Sum and Bicriteria Path

This page was built for publication: On Integer Programming and Convolution.