Cover Image

A unified worst case for classical simplex and policy iteration pivot rules

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Disser, Yann, Mosis, Nils
Format:	Preprint
Published:	2023
Subjects:	Discrete Mathematics Computational Complexity Data Structures and Algorithms Combinatorics 90C05 (Primary) 90C40 (Secondary) F.2.2; G.1.6; G.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

An unconditional lower bound for the active-set method on the hypercube
by: Disser, Yann, et al.
Published: (2025)

Loop unrolling of UCA models: distance labeling
by: Soulignac, Francisco J, et al.
Published: (2022)

Simple Approximations for General Spanner Problems
by: Bökler, Fritz, et al.
Published: (2025)

Exact Minimum Weight Spanners via Column Generation
by: Bökler, Fritz, et al.
Published: (2024)

Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
by: Chimani, Markus, et al.
Published: (2021)

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

An improved approximation algorithm for k-Median
by: Young, Neal E.
Published: (2025)

Computing distances is FPT on graph associahedra and W[2]-hard on hypergraphic polytopes
by: Cunha, Luís Felipe I., et al.
Published: (2025)

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

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

Cluster deletion and clique partitioning in graphs with bounded clique number
by: Galesi, Nicola, et al.
Published: (2025)

Explicit two-sided unique-neighbor expanders
by: Hsieh, Jun-Ting, et al.
Published: (2023)

An unconditional lower bound for the active-set method in convex quadratic maximization
by: Bach, Eleon, et al.
Published: (2025)

Color-Constrained Arborescences in Edge-Colored Digraphs
by: Ardra, P. S., et al.
Published: (2025)

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

A counterexample to the conjecture on Biclique Partition number of Split Graphs and related problems
by: Babu, Anand, et al.
Published: (2026)

Output-sensitive Complexity of Multi-Objective Integer Network Flow Problems
by: Könen, David, et al.
Published: (2023)

Extended Dijkstra algorithm and Moore-Bellman-Ford algorithm
by: Cheng, Cong-Dian
Published: (2017)

Solving the Graph Burning Problem for Large Graphs
by: Pereira, Felipe de Carvalho, et al.
Published: (2024)

Graph burning: an overview of mathematical programs
by: Cajica-Maceda, Lourdes Beatriz, et al.
Published: (2025)

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

m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs
by: Calamoneri, Tiziana, et al.
Published: (2025)

The Minimum Eternal Vertex Cover Problem on a Subclass of Series-Parallel Graphs
by: Calamoneri, Tiziana, 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)

On Relaxation of Dominant Sets
by: Koster, Max
Published: (2022)

Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
by: Bonnet, Édouard, et al.
Published: (2023)

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

Beyond Worst-Case Subset Sum: An Adaptive, Structure-Aware Solver with Sub-$2^{n/2}$ Enumeration
by: Salas, Jesus
Published: (2025)

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

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

Asymmetry in the Complexity of the Multi-Commodity Network Pricing Problem
by: Bui, Quang Minh, et al.
Published: (2022)

On modeling NP-Complete problems as polynomial-sized linear programs: Escaping/Side-stepping the "barriers"
by: Diaby, Moustapha, et al.
Published: (2023)

A New Temporal Interpretation of Cluster Editing
by: Bocci, Cristiano, et al.
Published: (2022)

On the Importance of Studying the Membership Problem for Pedigree Polytopes
by: Arthanari, Tiru
Published: (2025)

Tree-independence number VI. Thetas and pyramids
by: Chudnovsky, Maria, et al.
Published: (2025)

List Coloring of some Cayley graphs using Kernel perfections
by: S, Prajnanaswaroopa
Published: (2024)

Alon-Tarsi Number of Some Regular Graphs
by: Prajnanaswaroopa, S.
Published: (2023)

Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection
by: Coppé, Vianney, et al.
Published: (2022)