Sayan Bhattacharya

David Wajc

J. ACM, October, 2024

Fully Dynamic k-Clustering with Fast Update Time and Small Recourse.

[BibT_eX]

[DOI]

CoRR, 2024

Faster (Δ + 1)-Edge Coloring: Breaking the m √n Time Barrier.

[BibT_eX]

[DOI]

CoRR, 2024

Arboricity-Dependent Algorithms for Edge Coloring.

[BibT_eX]

[DOI]

Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory, 2024

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time.

[BibT_eX]

[DOI]

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

Dynamic Facility Location in High Dimensional Euclidean Spaces.

[BibT_eX]

[DOI]

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Density-Sensitive Algorithms for (Δ + 1)-Edge Coloring.

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023

Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover.

[BibT_eX]

[DOI]

SIAM J. Comput., October, 2023

Sublinear Algorithms for (1.5+ε)-Approximate Matching.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates.

[BibT_eX]

[DOI]

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

Fully Dynamic k-Clustering in Õ(k) Update Time.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Chasing Positive Bodies.

[BibT_eX]

[DOI]

Niv Buchbinder

Roie Levin

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Fully Dynamic (Δ +1)-Coloring in O(1) Update Time.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2022

A New Dynamic Algorithm for Densest Subhypergraphs.

[BibT_eX]

[DOI]

Proceedings of the WWW '22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25, 2022

Efficient and Stable Fully Dynamic Facility Location.

[BibT_eX]

[DOI]

Silvio Lattanzi

Nikos Parotsidis

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

Simple Dynamic Spanners with Near-Optimal Recourse Against an Adaptive Adversary.

[BibT_eX]

[DOI]

Pattara Sukprasert

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

Dynamic Set Cover: Improved Amortized and Worst-Case Update Time.

[BibT_eX]

[DOI]

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

Online Edge Coloring Algorithms via the Nibble Method.

[BibT_eX]

[DOI]

Fabrizio Grandoni

David Wajc

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

Deterministic Rounding of Dynamic Fractional Matchings.

[BibT_eX]

[DOI]

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

2020

Prior-free multi-unit auctions with ordered bidders.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

An Improved Algorithm for Dynamic Set Cover.

[BibT_eX]

[DOI]

CoRR, 2020

Deterministic Dynamic Matching in O(1) Update Time.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Algorithmica, 2020

Coarse-Grained Complexity for Dynamic Algorithms.

[BibT_eX]

[DOI]

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

An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs.

[BibT_eX]

[DOI]

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

2019

New amortized cell-probe lower bounds for dynamic problems.

[BibT_eX]

[DOI]

Stefan Neumann

Theor. Comput. Sci., 2019

Fully Dynamic (Δ+1)-Coloring in Constant Update Time.

[BibT_eX]

[DOI]

CoRR, 2019

Deterministically Maintaining a (2 + ∊)-Approximate Minimum Vertex Cover in O(1/∊2) Amortized Update Time.

[BibT_eX]

[DOI]

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

A New Deterministic Algorithm for Dynamic Set Cover.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.

[BibT_eX]

[DOI]

Giuseppe F. Italiano

SIAM J. Comput., 2018

Dynamic algorithms via the primal-dual method.

[BibT_eX]

[DOI]

Giuseppe F. Italiano

Inf. Comput., 2018

Deterministically Maintaining a (2+ε)-Approximate Minimum Vertex Cover in O(1/ε2) Amortized Update Time.

[BibT_eX]

[DOI]

CoRR, 2018

Dynamic Algorithms for Graph Coloring.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

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

2017

Welfare Maximization with Friends-of-Friends Network Externalities.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2017

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3n) Worst Case Update Time.

[BibT_eX]

[DOI]

CoRR, 2017

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time.

[BibT_eX]

[DOI]

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

Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Improved Algorithm for Dynamic b-Matching.

[BibT_eX]

[DOI]

Manoj Gupta

Divyarthi Mohan

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016

New deterministic approximation algorithms for fully dynamic matching.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams.

[BibT_eX]

[DOI]

Charalampos E. Tsourakakis

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Design of Dynamic Algorithms via Primal-Dual Method.

[BibT_eX]

[DOI]

Giuseppe F. Italiano

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Maintaining Near-Popular Matchings.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

New Approximability Results for the Robust k-Median Problem.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory - SWAT 2014, 2014

Coordination mechanisms from (almost) all scheduling policies.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2014

Coordination Mechanisms for Selfish Routing over Time on a Tree.

[BibT_eX]

[DOI]

Vahab S. Mirrokni

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Near-optimal multi-unit auctions with ordered bidders.

[BibT_eX]

[DOI]

Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

2012

Budget-Constrained Auctions with Heterogeneous Items.

[BibT_eX]

[DOI]

Theory Comput., 2012

Constant-Competitive Prior-Free Auction with Ordered Bidders

[BibT_eX]

[DOI]

Xiaoming Xu

CoRR, 2012

Computing a Profit-Maximizing Sequence of Offers to Agents in a Social Network.

[BibT_eX]

[DOI]

Dmytro Korzhyk

Vincent Conitzer

Proceedings of the Internet and Network Economics - 8th International Workshop, 2012

2011

Consideration set generation in commerce search.

[BibT_eX]

[DOI]

Sreenivas Gollapudi

Kamesh Munagala

Proceedings of the 20th International Conference on World Wide Web, 2011

On Allocations with Negative Externalities.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics - 7th International Workshop, 2011

Approximation Algorithm for Security Games with Costly Resources.

[BibT_eX]

[DOI]

Vincent Conitzer

Kamesh Munagala

Proceedings of the Internet and Network Economics - 7th International Workshop, 2011

2010

A cops and robber game in multidimensional grids.

[BibT_eX]

[DOI]

Goutam Paul

Swagato Sanyal

Discret. Appl. Math., 2010

Incentive Compatible Budget Elicitation in Multi-unit Auctions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

On Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids

[BibT_eX]

[DOI]