Cover Image

From approximate to exact integer programming

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dadush, Daniel, Eisenbrand, Friedrich, Rothvoss, Thomas
Format:	Preprint
Published:	2022
Subjects:	Optimization and Control Computational Complexity Discrete Mathematics Data Structures and Algorithms Combinatorics 15A, 52B, 52C, 68Q, 68R, 68W, 90B, 90C F.2.2; G.1.6
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Subspace Flatness Conjecture and Faster Integer Programming
by: Reis, Victor, et al.
Published: (2023)

Degree Sequence Optimization and Extremal Degree Enumerators
by: Onn, Shmuel
Published: (2024)

Circuit and Graver Walks and Linear and Integer Programming
by: Onn, Shmuel
Published: (2024)

The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
by: Heimann, Sophia, et al.
Published: (2024)

The Bottom-Left Algorithm for the Strip Packing Problem
by: Hougardy, Stefan, et al.
Published: (2024)

A New Algorithm for Computing Integer Hulls of 2D Polyhedral Sets
by: Mukherjee, Chirantan
Published: (2025)

A Speed-up for Helsgaun's TSP Heuristic by Relaxing the Positive Gain Criterion
by: Ammann, Sabrina C. L., et al.
Published: (2024)

A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem
by: Heimann, Sophia, et al.
Published: (2025)

Packing, Hitting, and Colouring Squares
by: Caoduro, Marco, et al.
Published: (2022)

On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions
by: Laekhanukit, Bundit
Published: (2024)

Extending Exact Integrality Gap Computations for the Metric TSP
by: Cook, William, et al.
Published: (2026)

On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem
by: Heimann, Sophia, et al.
Published: (2026)

Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy
by: Feldman, Moran, et al.
Published: (2026)

A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads
by: Rockel-Wolff, Benjamin
Published: (2024)

Pliability and Approximating Max-CSPs
by: Romero, Miguel, et al.
Published: (2019)

Efficient Decomposition of Forman-Ricci Curvature on Vietoris-Rips Complexes and Data Applications
by: de Souza, Danillo Barros, et al.
Published: (2025)

Revisiting Chazelle's Implementation of the Bottom-Left Heuristic: A Corrected and Rigorous Analysis
by: Michel, Stefan
Published: (2025)

On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces
by: Emmerich, Michael T. M., et al.
Published: (2026)

Exact Dynamic Programming for Solow--Polasky Diversity Subset Selection on Lines and Staircases
by: Emmerich, Michael T. M.
Published: (2026)

New Theoretical Insights and Algorithmic Solutions for Reconstructing Score Sequences from Tournament Score Sets
by: Liu, Bowen
Published: (2025)

Greedy and randomized heuristics for optimization of k-domination models in digraphs and road networks
by: Dijkstra, Lukas, et al.
Published: (2024)

A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm
by: Hougardy, Stefan, et al.
Published: (2025)

Bicriteria Submodular Maximization
by: Feldman, Moran, et al.
Published: (2025)

Polyhedral approach to weighted connected matchings in general graphs
by: Samer, Phillippe, et al.
Published: (2023)

Robinson spaces and their representation in low-dimensional metric spaces
by: Arrepol, Francisco, et al.
Published: (2026)

Lower bounds and integrality gaps in simplicial decomposition
by: Ellison, Matthew
Published: (2024)

The frequency $K_i$s for symmetrical traveling salesman problem
by: Wang, Yong
Published: (2025)

Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses
by: Ye, Yuhan
Published: (2026)

On the Hardness of Short and Sign-Compatible Circuit Walks
by: Borgwardt, Steffen, et al.
Published: (2024)

Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint
by: Buchbinder, Niv, et al.
Published: (2024)

Attempting the impossible: enumerating extremal submodular functions for n=6
by: Csirmaz, Elod P., et al.
Published: (2024)

Optimal Hardness of Online Algorithms for Large Independent Sets
by: Gamarnik, David, et al.
Published: (2025)

Modern column generation for estimating single- and multi-purchase ranked list choice models
by: Costa, Luciano, et al.
Published: (2026)

Blended Conditional Gradients: the unconditioning of conditional gradients
by: Braun, Gábor, et al.
Published: (2018)

Weighted domination models and randomized heuristics
by: Dijkstra, Lukas, et al.
Published: (2022)

Supermodular Maximization with Cardinality Constraints
by: Chen, Xujin, et al.
Published: (2025)

Proof-Carrying Verification for ReLU Networks via Rational Certificates
by: Gokavarapu, Chandrasekhar
Published: (2025)

Approximation algorithms for the prize-collecting rural postman problem
by: Li, Hong, et al.
Published: (2026)

Optimal Online Bipartite Matching in Degree-2 Graphs
by: Bhangale, Amey, et al.
Published: (2025)

Learning Decision-Sufficient Representations for Linear Optimization
by: Ye, Yuhan, et al.
Published: (2026)