Cover Image

Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Schade, Jamico, Sinha, Makrand, Weltge, Stefan
Format:	Preprint
Published:	2023
Subjects:	Discrete Mathematics Data Structures and Algorithms Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Integer programs with bounded subdeterminants and two nonzeros per row
by: Fiorini, Samuel, et al.
Published: (2021)

Integer programs with nearly totally unimodular matrices: the cographic case
by: Aprile, Manuel, et al.
Published: (2024)

Multiplicative assignment with upgrades
by: Armbruster, Alexander, et al.
Published: (2025)

Efficient Local and Tabu Search Strategies for Large-Scale Quadratic Integer Programming
by: Wang, Haibo, et al.
Published: (2024)

Better and Simpler Reducibility Bounds over the Integers
by: Levin, Asaf
Published: (2025)

Max-Min and 1-Bounded Space Algorithms for the Bin Packing Problem
by: Fujiwara, Hiroshi, et al.
Published: (2025)

Totally $Δ$-modular IPs with two non-zeros in most rows
by: Kober, Stefan
Published: (2024)

Generalized Nash Equilibrium Problems with Mixed-Integer Variables
by: Harks, Tobias, et al.
Published: (2021)

Complexity of polytope diameters via perfect matchings
by: Nöbel, Christian, et al.
Published: (2024)

A Primal-Dual Extension of the Goemans--Williamson Algorithm for the Weighted Fractional Cut-Covering Problem
by: Proença, Nathan Benedetto, et al.
Published: (2023)

Flow Shop Scheduling with Stochastic Reentry
by: von Aspern, Maximilian, et al.
Published: (2026)

Generalized Cuts and Grothendieck Covers: a Primal-Dual Approximation Framework Extending the Goemans--Williamson Algorithm
by: Proença, Nathan Benedetto, et al.
Published: (2024)

New Sequence-Independent Lifting Techniques for Cutting Planes and When They Induce Facets
by: Prasad, Siddharth, et al.
Published: (2024)

A 1/2-Approximation for Budgeted $k$-Submodular Maximization
by: Wang, Chenhao
Published: (2025)

ResQue Greedy: Rewiring Sequential Greedy for Improved Submodular Maximization
by: Gallart, Joan Vendrell, et al.
Published: (2025)

Total Matching and Subdeterminants
by: Ferrarini, Luca, et al.
Published: (2023)

Difference of Submodular Minimization via DC Programming
by: Halabi, Marwa El, et al.
Published: (2023)

A Tie-breaking based Local Search Algorithm for Stable Matching Problems
by: Qiu, Junyuan
Published: (2024)

On the Congruency-Constrained Matroid Base
by: Liu, Siyue, et al.
Published: (2023)

Vertex-ordering and arc-partitioning problems
by: Borsik, Nóra A., et al.
Published: (2025)

Separable convex optimization over indegree polytopes
by: Borsik, Nóra A., et al.
Published: (2025)

Prefix-bounded matrices
by: Borsik, Nóra A., et al.
Published: (2025)

Periodic trajectories in P-time event graphs and the non-positive circuit weight problem
by: Zorzenon, Davide, et al.
Published: (2021)

Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
by: Klimm, Max, et al.
Published: (2022)

Semidefinite programming and linear equations vs. homomorphism problems
by: Ciardo, Lorenzo, et al.
Published: (2023)

Simultaneous Network Design with Restricted Link Usage
by: Kakimura, Naonori, et al.
Published: (2025)

Parallel Token Swapping for Qubit Routing
by: Bansal, Ishan, et al.
Published: (2024)

An Exact Solver for Submodular Knapsack Problems
by: Münch, Sabine, et al.
Published: (2025)

Robust Permutation Flowshops Under Budgeted Uncertainty
by: Goldberg, Noam, et al.
Published: (2026)

Efficient approximation schemes for scheduling on a stochastic number of machines
by: Epstein, Leah, et al.
Published: (2024)

Algorithmic aspects of semistability of quiver representations
by: Iwamasa, Yuni, et al.
Published: (2024)

NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
by: Kar, Prem Nigam, et al.
Published: (2024)

A Θ(m^9) ternary minimum-cost network flow LP model of the Assignment Problem polytope with applications to hard combinatorial optimization problems
by: Diaby, Moustapha
Published: (2016)

Parameterized Complexity of Path Set Packing
by: Aravind, N. R., et al.
Published: (2022)

Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets
by: Marin, Malory
Published: (2025)

A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line
by: Harada, Tsubasa
Published: (2024)

Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
by: Efthymiou, Charilaos, et al.
Published: (2023)

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
by: Bentert, Matthias, et al.
Published: (2024)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
by: Arndt, Stephen, et al.
Published: (2026)

Parameterized Complexity of s-Club Cluster Edge Deletion: When Is the Diameter Bound Necessary?
by: Gaikwad, Ajinkya
Published: (2025)