Cover Image

Optimal Extended Formulations from Optimal Dynamic Programming Algorithms

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Oliveira, Mateus de Oliveira, Broeck, Wim Van den
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Symbolic Functional Decomposition: A Reconfiguration Approach
by: Oliveira, Mateus de Oliveira, et al.
Published: (2026)

Algorithms for Optimizing Acyclic Queries
by: Luo, Zheng, et al.
Published: (2025)

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
by: Gorbachev, Egor, et al.
Published: (2024)

An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning
by: Xu, Chao, et al.
Published: (2026)

Optimal Learning-Augmented Algorithm for Online Bidding
by: Lee, Changyeol, et al.
Published: (2026)

Simple and Optimal Sublinear Algorithms for Mean Estimation
by: Bertolotti, Beatrice, et al.
Published: (2024)

An Optimal Algorithm for Sorting Pattern-Avoiding Sequences
by: Opler, Michal
Published: (2024)

Near-Optimal Algorithm for Directed Expander Decompositions
by: Sulser, Aurelio L., et al.
Published: (2024)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
by: Das, Debarati, et al.
Published: (2026)

(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs
by: Hunkenschröder, Christoph, et al.
Published: (2025)

An Optimal Sorting Algorithm for Persistent Random Comparison Faults
by: Geissmann, Barbara, et al.
Published: (2025)

A Note on the Conditional Optimality of Chiba and Nishizeki's Algorithms
by: Kirkpatrick, Yael, et al.
Published: (2024)

Optimal Algorithms for Free Order Multiple-Choice Secretary
by: Hajiaghayi, Mohammad Taghi, et al.
Published: (2022)

From Dynamic Programs to Greedy Algorithms
by: van Melkebeek, Dieter
Published: (2025)

An $O(n^5)$-Time Algorithm for Optimal Broadcast Domination
by: Papadopoulos, Kleitos
Published: (2026)

Algorithms for Optimally Shifting Intervals under Intersection Graph Models
by: Honorato-Droguett, Nicolás, et al.
Published: (2023)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Optimal Neighborhood Exploration for Dynamic Independent Sets
by: Borowitz, Jannick, et al.
Published: (2024)

(Worst-Case) Optimal Adaptive Dynamic Bitvectors
by: Navarro, Gonzalo
Published: (2024)

Dynamic Suffix Array in Optimal Compressed Space
by: Nishimoto, Takaaki, et al.
Published: (2024)

An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with Applications to LIS
by: Koo, Jaehyun
Published: (2024)

Effective Index Construction Algorithm for Optimal $(k,η)$-cores Computation
by: Sun, Shengli, et al.
Published: (2025)

Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models
by: Huang, Zengfeng, et al.
Published: (2025)

Optimal-Length Labeling Schemes and Fast Algorithms for k-gathering and k-broadcasting
by: Ganczorz, Adam, et al.
Published: (2025)

Optimality of Non-Adaptive Algorithms in Online Submodular Welfare Maximization with Stochastic Outcomes
by: Udwani, Rajan
Published: (2024)

A Practical Linear Time Algorithm for Optimal Tree Decomposition of Halin Graphs
by: Alejandro-Soto, J. A., et al.
Published: (2025)

Near-Optimal Algorithms for Omniprediction
by: Okoroafor, Princewill, et al.
Published: (2025)

Approximation Algorithms for Optimal Hopsets
by: Dinitz, Michael, et al.
Published: (2025)

Dynamic Grammar-Compressed Self-Index in $δ$-Optimal Space
by: Nishimoto, Takaaki, et al.
Published: (2026)

Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
by: Bhattacharya, Sayan, et al.
Published: (2023)

Optimal Algorithm for Paired-Domination in Distance-Hereditary Graphs
by: Mu, Ta-Yu, et al.
Published: (2024)

A Simple, Nearly-Optimal Algorithm for Differentially Private All-Pairs Shortest Distances
by: Campbell, Jesse, et al.
Published: (2024)

Unbiased Insights: Optimal Streaming Algorithms for $\ell_p$ Sampling, the Forget Model, and Beyond
by: Lin, Honghao, et al.
Published: (2025)

Optimal Dynamic Parameterized Subset Sampling
by: Gan, Junhao, et al.
Published: (2024)

Anytime Sorting Algorithms (Extended Version)
by: Caizergues, Emma, et al.
Published: (2024)

Fully Dynamic k-Means Coreset in Near-Optimal Update Time
by: la Tour, Max Dupré, et al.
Published: (2024)

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

A canonical generalization of OBDD
by: Capelli, Florent, et al.
Published: (2026)