#linear programming
12 papers · 1 filter
An LP Algorithm for Counting Eulerian Orientations Through the Lens of Quasi-polymorphism
Jincheng Guan, Shuai Shao, Ke Shi
The paper provides a polynomial-time algorithm for counting weighted Eulerian orientations in cases previously only known to be in FP^NP, using a linear programming relaxation to t…
Approximate Dual Separation for the Cluster LP: a 1.387 approximation for Correlation Clustering
David GarcÃa-Soriano, Antoine Schohn
The paper presents a (1.3865+ε)-approximation algorithm for correlation clustering on complete graphs by introducing an efficient approximate dual separation oracle for the cluster…
Counterexamples, Spectral Obstructions, and Deletion Stability for WOW-284
Samuil Petkov
The paper disproves the WOW‑284 conjecture by presenting exact counterexample graphs of orders 38, 39, 40, 42, and 50, and develops a structural theory describing the failure, incl…
Using a MIP Solver as a PDHG-Based MIP Heuristic
Edward Rothberg
The paper explores using the PDHG algorithm as a fast, low‑accuracy LP solver within mixed‑integer programming solvers to speed up existing heuristics for finding feasible, high‑qu…
Fixed-Parameter Tractability of Private Synthetic Data Generation
Badih Ghazi, Cristóbal Guzmán, Pritish Kamath +3
The paper investigates generating differentially private synthetic data and shows that the problem is fixed-parameter tractable when parameterized by the treewidth of the query fam…
Arithmetic Sparsity and Obstructions in Weighted Projective Spaces
Tanush Shaska
The paper studies the distribution of rational and algebraic points of bounded height on weighted projective spaces, proving asymptotic counting formulas for two natural height fun…