(home)   //   (publications)   //   (blog)   //   (scans from the library)

A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix

PDF

arXiv

BibTeX

@article{lls,
  doi = {10.1007/s10107-023-01956-2},
  year = {2023},
  month = apr,
  publisher = {Springer Science and Business Media {LLC}},
  author = {Daniel Dadush and Sophie Huiberts and Bento Natura and L{\'{a}}szl{\'{o}} A. V{\'{e}}gh},
  title = {A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix},
  archivePrefix={arXiv},
  eprint={1912.06252},
  journal = {Mathematical Programming},
  note={preliminary version in STOC 2020}
}

A nearly optimal randomized algorithm for explorable heap selection (Oct 2022)
 Sander Borst, Daniel Dadush, Sophie Huiberts, Danish Kashaev.
 IPCO 2023, Mathematical Programming / arXiv / talk / bibTeX
On the Integrality Gap of Binary Integer Programs with Gaussian Data (Dec 2020)
 Sander Borst, Daniel Dadush, Sophie Huiberts, Samarth Tiwari.
 IPCO 2021, Mathematical Programming / arXiv / bibTeX