Optimal Extended Formulations from Optimal Dynamic Programming Algorithms
Authors: Mateus de Oliveira Oliveira, Wim Van den Broeck
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we establish a sharp connection between both approaches by showing that if a vertex-subset problem Π admits a solution-preserving dynamic programming algorithm that produces tables of size at most α(k, n) when processing a tree decomposition of width at most k of an n-vertex graph G, then the polytope PΠ(G) defined as the convex-hull of solutions of Π in G has extension complexity at most O(α(k, n) n). Additionally, this upper bound is optimal under the exponential time hypothesis (ETH). |
| Researcher Affiliation | Academia | Department of Computer and Systems Sciences, Stockholm University, Sweden Department of Informatics, University of Bergen, Norway |
| Pseudocode | No | The paper describes the components of a DP-core and provides an example for Independent Set by specifying actions for Leaf, Intro Vertex, etc. This is a description of an algorithm's logic, but not a formally structured pseudocode or algorithm block. |
| Open Source Code | No | The paper does not provide concrete access to source code. There are no links to repositories or explicit statements about code availability. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments involving datasets. It discusses combinatorial problems like INDEPENDENT SET as mathematical examples, not as empirical datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments with dataset splits. Therefore, no specific dataset split information for validation is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments that would require specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe experiments that would require specific software dependencies. No specific ancillary software details with version numbers are provided. |
| Experiment Setup | No | The paper is theoretical and does not describe experiments. Therefore, no specific experimental setup details (like hyperparameters or training configurations) are provided. |