Cover Image

The Subspace Flatness Conjecture and Faster Integer Programming

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Reis, Victor, Rothvoss, Thomas
Format:	Preprint
Published:	2023
Subjects:	Optimization and Control Computational Complexity Discrete Mathematics Data Structures and Algorithms Combinatorics 15A, 52A, 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

From approximate to exact integer programming
by: Dadush, Daniel, et al.
Published: (2022)

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

Degree Sequence Optimization and Extremal Degree Enumerators
by: Onn, Shmuel
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)

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

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)

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

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

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

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

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

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

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

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

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

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

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)

On the Geometric Convergence of Byzantine-Resilient Distributed Optimization Algorithms
by: Kuwaranancharoen, Kananart, et al.
Published: (2023)

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

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

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

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

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

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

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

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

General Constrained Matrix Optimization
by: Garner, Casey, et al.
Published: (2024)

Spectrally Constrained Optimization
by: Garner, Casey, et al.
Published: (2023)

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

A Heuristic Alternating Direction Method of Multipliers Framework for Distributed and Centralized Tree-Constrained Optimization: Applications to Hop-Constrained Spanning Tree Multicommodity Flow Design
by: Mokhtari, Yacine
Published: (2025)

On Supmodular Matrices
by: Onn, Shmuel
Published: (2023)

Critical moments of slices and slabs of the cube (and other polyhedral norms)
by: Brandenburg, Marie-Charlotte, et al.
Published: (2026)

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

Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints
by: Schwardt, J., et al.
Published: (2025)

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
by: Lagerkvist, Victor, et al.
Published: (2026)

Uniform Value and Decidability in Ergodic Blind Stochastic Games
by: Chatterjee, Krishnendu, et al.
Published: (2024)