Imagen de Portada

Solving 4-Block Integer Linear Programs Faster Using Affine Decompositions of the Right-Hand Sides

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Lassota, Alexandra, Ligthart, Koen
Formato:	Preprint
Publicado:	2026
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Parameterized Algorithms for Matching Integer Programs with Additional Rows and Columns
por: Lassota, Alexandra, et al.
Publicado: (2025)

Tight Lower Bounds for Block-Structured Integer Programs
por: Hunkenschröder, Christoph, et al.
Publicado: (2024)

Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
por: Lichter, Moritz, et al.
Publicado: (2024)

Relating the Computational and Logical Difficulty of Solving ODEs: From Polynomial to Discontinuous Right-Hand Sides
por: Bournez, Olivier, et al.
Publicado: (2026)

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
por: Li, Xin, et al.
Publicado: (2023)

Automatizing Software Cognitive Complexity Reduction through Integer Linear Programming
por: Saborido, Rubén, et al.
Publicado: (2024)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
por: Rohwedder, Lars, et al.
Publicado: (2024)

Computational Complexity and Integer Programming Formulation of the Oredango Puzzle
por: Takahata, Takuma, et al.
Publicado: (2025)

Integer Programming Using A Single Atom
por: Goswami, Kapil, et al.
Publicado: (2024)

Affine Rank Minimization is ER Complete
por: Majumdar, Angshul
Publicado: (2026)

A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions
por: Ketkov, Sergey S., et al.
Publicado: (2025)

Faster search for tensor decomposition over finite fields
por: Yang, Jason
Publicado: (2025)

Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Integer Linear Arithmetic
por: Gokaj, Geri, et al.
Publicado: (2025)

Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
por: Wang, Qisheng, et al.
Publicado: (2024)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
por: Gibor, Daniel
Publicado: (2025)

Two-Source and Affine Non-Malleable Extractors for Small Entropy
por: Li, Xin, et al.
Publicado: (2024)

Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
por: Ani, Hayashi, et al.
Publicado: (2024)

Counterfactual Explanations for Integer Optimization Problems
por: Engelhardt, Felix, et al.
Publicado: (2025)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
por: Esmer, Barış Can, et al.
Publicado: (2022)

Parameterized Complexity of the Star Decomposition Problem
por: Hajebi, Sahab, et al.
Publicado: (2024)

The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
por: Asimi, Kristina, et al.
Publicado: (2024)

An Efficient Algorithm for Solving the 2-MAXSAT Problem
por: Chen, Yangjun
Publicado: (2023)

Faster Mixing of Higher-Dimensional Random Reversible Circuits
por: Gay, William, et al.
Publicado: (2024)

Low-Rank Tensor Decomposition over Finite Fields
por: Yang, Jason
Publicado: (2024)

Faster Convolutions: Yates and Strassen Revisited
por: Brand, Cornelius, et al.
Publicado: (2025)

On Big-M Reformulations of Bilevel Linear Programs: Hardness of A Posteriori Verification
por: Ketkov, Sergey S., et al.
Publicado: (2026)

New Limits on Distributed Quantum Advantage: Dequantizing Linear Programs
por: Balliu, Alkida, et al.
Publicado: (2025)

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

Faster algorithms for graph homomorphism via tractable constraint satisfaction
por: Carbonnel, Clément
Publicado: (2026)

When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames
por: Krebs, Andreas, et al.
Publicado: (2025)

Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice
por: Digulescu, Mircea-Adrian
Publicado: (2026)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
por: Nalli, Sai Soumya, et al.
Publicado: (2026)

More Asymmetry Yields Faster Matrix Multiplication
por: Alman, Josh, et al.
Publicado: (2024)

You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games
por: MIT Hardness Group, et al.
Publicado: (2024)

A Critique of Chen's "The 2-MAXSAT Problem Can Be Solved in Polynomial Time"
por: Le, Tran Duy Anh, et al.
Publicado: (2024)

Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
por: MIT Hardness Group, et al.
Publicado: (2025)

Ruling Out Low-rank Matrix Multiplication Tensor Decompositions with Symmetries via SAT
por: Yang, Jason
Publicado: (2024)

Biased Linearity Testing in the 1% Regime
por: Khot, Subhash, et al.
Publicado: (2025)

Isomorphism Testing of Rooted Trees in Linear Time
por: Lindeberg, Anna
Publicado: (2024)

The Parameterized Complexity of Computing the Linear Vertex Arboricity
por: Erhardt, Alexander, et al.
Publicado: (2025)