Kent Quanrud

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Faster exact and approximation algorithms for packing and covering matroids via push-relabel.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Adaptive Out-Orientations with Applications.

[BibT_eX]

[DOI]

Aleksander Bjørn Grodt Christiansen

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Approximate Fully Dynamic Directed Densest Subgraph.

[BibT_eX]

[DOI]

Richard Li

CoRR, 2023

Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing.

[BibT_eX]

[DOI]

Elfarouk Harb

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

Independent Sets in Elimination Graphs with a Submodular Objective.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2023

2022

Fast and Deterministic Approximations for k-Cut.

[BibT_eX]

[DOI]

Theory Comput., 2022

Algorithms for covering multiple submodular constraints and applications.

[BibT_eX]

[DOI]

Tanmay Inamdar

Kasturi R. Varadarajan

Zhao Zhang

J. Comb. Optim., 2022

(1-ε)-approximate fully dynamic densest subgraph: linear space and faster update time.

[BibT_eX]

[DOI]

CoRR, 2022

Densest Subgraph: Supermodularity, Iterative Peeling, and Flow.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Faster and Scalable Algorithms for Densest Subgraph and Decomposition.

[BibT_eX]

[DOI]

Elfarouk Harb

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

2021

Fast Approximations for Rooted Connectivity in Weighted Directed Graphs.

[BibT_eX]

[DOI]

CoRR, 2021

Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Global Connectivity Problems.

[BibT_eX]

[DOI]

CoRR, 2021

Spectral Sparsification of Metrics and Kernels.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Connectivity.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Faster Algorithms for Rooted Connectivity in Directed Graphs.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Minimum Cuts in Directed Graphs via Partial Sparsification.

[BibT_eX]

[DOI]

Thatchaphol Saranurak

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Online Directed Spanners and Steiner Forests.

[BibT_eX]

[DOI]

Elena Grigorescu

Young-San Lin

Proceedings of the Approximation, 2021

Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

LP Relaxation and Tree Packing for Minimum k-Cut.

[BibT_eX]

[DOI]

Chao Xu

SIAM J. Discret. Math., 2020

ℓ <sub>1</sub>-Sparsity approximation bounds for packing integer programs.

[BibT_eX]

[DOI]

Math. Program., 2020

Nearly linear time approximations for mixed packing and covering problems without data structures or randomization.

[BibT_eX]

[DOI]

Proceedings of the 3rd Symposium on Simplicity in Algorithms, 2020

Computing Circle Packing Representations of Planar Graphs.

[BibT_eX]

[DOI]

Sally Dong

Yin Tat Lee

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Fast LP-based Approximations for Geometric Packing and Covering Problems.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

Fast approximations for combinatorial optimization via multiplicative weight updates

[BibT_eX]

[DOI]

PhD thesis, 2019

On Approximating Partial Set Cover and Generalizations.

[BibT_eX]

[DOI]

Zhao Zhang

CoRR, 2019

$\ell_1$-sparsity Approximation Bounds for Packing Integer Programs.

[BibT_eX]

[DOI]

CoRR, 2019

Parallelizing greedy for submodular set function maximization in matroids and beyond.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Approximating Optimal Transport With Linear Programs.

[BibT_eX]

[DOI]

Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

On Approximating (Sparse) Covering Integer Programs.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Submodular Function Maximization in Parallel via the Multilinear Relaxation.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

LP Relaxation and Tree Packing for Minimum k-cuts.

[BibT_eX]

[DOI]

Chao Xu

Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

\ell _1 -sparsity Approximation Bounds for Packing Integer Programs.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2019

2018

Fast Approximations for Metric-TSP via Linear Programming.

[BibT_eX]

[DOI]

CoRR, 2018

Randomized MWU for Positive LPs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Near-Linear Time Approximation Schemes for some Implicit Fractional Packing Problems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Notes on Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs.

[BibT_eX]

[DOI]

CoRR, 2016

A Fast Approximation for Maximum Weight Matroid Intersection.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

Approximation Algorithms for Low-Density Graphs.

[BibT_eX]

[DOI]

CoRR, 2015

Online Learning with Adversarial Delays.

[BibT_eX]

[DOI]

Daniel Khashabi

Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Streaming Algorithms for Submodular Function Maximization.

[BibT_eX]

[DOI]

Shalmoli Gupta