David Wajc

Publication Activity (10 Years)

Years Active: 2011-2024
Publications (10 Years): 55

Top Topics

Bipartite Matching

Greedy Algorithm

Completion Times

Targeted Advertising

Top Venues

Publications

Kshipra Bhawalkar, Zhe Feng, Anupam Gupta, Aranyak Mehta, David Wajc, Di Wang
The Average-Value Allocation Problem. CoRR (2024)
Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc
Online Edge Coloring is (Nearly) as Easy as Offline. CoRR (2024)
Mark Braverman, Mahsa Derakhshan, Tristan Pollner, Amin Saberi, David Wajc
New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling. CoRR (2024)
Zhiyi Huang, Zhihao Gavin Tang, David Wajc
Online Matching: A Brief Survey. CoRR (2024)
Sayan Bhattacharya, Peter Kiss, Aaron Sidford, David Wajc
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs. STOC (2024)
Neel Patel, David Wajc
Combinatorial Stationary Prophet Inequalities. SODA (2024)
Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc
Online Edge Coloring Is (Nearly) as Easy as Offline. STOC (2024)
Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc
Simple and Asymptotically Optimal Online Bipartite Edge Coloring. SOSA (2024)
Sayan Bhattacharya, Peter Kiss, Aaron Sidford, David Wajc
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs. CoRR (2023)
Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc
Simple and Asymptotically Optimal Online Bipartite Edge Coloring. CoRR (2023)
Joseph Naor, Aravind Srinivasan, David Wajc
Online Dependent Rounding Schemes. CoRR (2023)
Neel Patel, David Wajc
Combinatorial Stationary Prophet Inequalities. CoRR (2023)
Niv Buchbinder, Joseph (Seffi) Naor, David Wajc
Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility). SODA (2023)
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David Wajc
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time. SODA (2023)
Mohammad Roghani, Amin Saberi, David Wajc
Beating the Folklore Algorithm for Dynamic Matching. ITCS (2022)
Tristan Pollner, Mohammad Roghani, Amin Saberi, David Wajc
Improved Online Contention Resolution for Matchings and Applications to the Gig Economy. CoRR (2022)
Tristan Pollner, Mohammad Roghani, Amin Saberi, David Wajc
Improved Online Contention Resolution for Matchings and Applications to the Gig Economy. EC (2022)
Kristen Kessel, Ali Shameli, Amin Saberi, David Wajc
The Stationary Prophet Inequality Problem. EC (2022)
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David Wajc
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time. CoRR (2022)
Amin Saberi, David Wajc
The Greedy Algorithm is \emph{not} Optimal for On-Line Edge Coloring. CoRR (2021)
Mohammad Roghani, Amin Saberi, David Wajc
Beating the Folklore Algorithm for Dynamic Matching. CoRR (2021)
Niv Buchbinder, Joseph Naor, David Wajc
A Randomness Threshold for Online Bipartite Matching, via Lossless Online Rounding. CoRR (2021)
Christos H. Papadimitriou, Tristan Pollner, Amin Saberi, David Wajc
Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities. EC (2021)
Christos H. Papadimitriou, Tristan Pollner, Amin Saberi, David Wajc
Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities. CoRR (2021)
Kristen Kessel, Amin Saberi, Ali Shameli, David Wajc
The Stationary Prophet Inequality Problem. CoRR (2021)
Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc
Near-Optimal Schedules for Simultaneous Multicasts. ICALP (2021)
Sayan Bhattacharya, Fabrizio Grandoni, David Wajc
Online Edge Coloring Algorithms via the Nibble Method. SODA (2021)
Bernhard Haeupler, David Wajc, Goran Zuzic
Universally-Optimal Distributed Algorithms for Known Topologies. CoRR (2021)
Bernhard Haeupler, David Wajc, Goran Zuzic
Universally-optimal distributed algorithms for known topologies. STOC (2021)
Roie Levin, David Wajc
Streaming Submodular Matching Meets the Primal-Dual Method. SODA (2021)
Amin Saberi, David Wajc
The Greedy Algorithm Is not Optimal for On-Line Edge Coloring. ICALP (2021)
Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc
Near-Optimal Schedules for Simultaneous Multicasts. CoRR (2020)
Sayan Bhattacharya, Fabrizio Grandoni, David Wajc
Online Edge Coloring Algorithms via the Nibble Method. CoRR (2020)
Bernhard Haeupler, David Wajc, Goran Zuzic
Network Coding Gaps for Completion Times of Multiple Unicasts. FOCS (2020)
Roie Levin, David Wajc
Streaming Submodular Matching Meets the Primal-Dual Method. CoRR (2020)
David Wajc
Rounding dynamic matchings against an adaptive adversary. STOC (2020)
Mohsen Ghaffari, David Wajc
Simplified and Space-Optimal Semi-Streaming (2+epsilon)-Approximate Matching. SOSA (2019)
Anupam Gupta, Guru Guruganesh, Binghui Peng, David Wajc
Stochastic Online Metric Matching. ICALP (2019)
Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, David Wajc
Online Matching with General Arrivals. CoRR (2019)
Ilan Reuven Cohen, Binghui Peng, David Wajc
Tight Bounds for Online Edge Coloring. FOCS (2019)
Bernhard Haeupler, David Wajc, Goran Zuzic
Network Coding Gaps for Completion Times of Multiple Unicasts. CoRR (2019)
David Wajc
Rounding Dynamic Matchings Against an Adaptive Adversary. CoRR (2019)
Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, David Wajc
Online Matching with General Arrivals. FOCS (2019)
Anupam Gupta, Guru Guruganesh, Binghui Peng, David Wajc
Stochastic Online Metric Matching. CoRR (2019)
Ilan Reuven Cohen, Binghui Peng, David Wajc
Tight Bounds for Online Edge Coloring. CoRR (2019)
Joseph (Seffi) Naor, David Wajc
Near-Optimum Online Ad Allocation for Targeted Advertising. ACM Trans. Economics and Comput. 6 (3-4) (2018)
Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc
Round- and Message-Optimal Distributed Graph Algorithms. PODC (2018)
Ariel D. Procaccia, David Wajc, Hanrui Zhang
Approximation-Variance Tradeoffs in Facility Location Games. AAAI (2018)
Ilan Reuven Cohen, David Wajc
Randomized Online Matching in Regular Graphs. SODA (2018)
Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc
Round- and Message-Optimal Distributed Part-Wise Aggregation. CoRR (2018)
Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, David Wajc
Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms. ICALP (2018)
Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar, Sören Riechers, David Wajc
Fully-Dynamic Bin Packing with Little Repacking. ICALP (2018)
Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, David Wajc
Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms. CoRR (2017)
Anupam Gupta, Guru Guruganesh, Amit Kumar, David Wajc
Fully-Dynamic Bin Packing with Limited Repacking. CoRR (2017)
Bernhard Haeupler, David Wajc
A Faster Distributed Radio Broadcast Primitive: Extended Abstract. PODC (2016)
Iftah Gamzu, Zohar Shay Karnin, Yoelle Maarek, David Wajc
You Will Get Mail!Predicting the Arrival of Future Email. WWW (Companion Volume) (2015)
Joseph Naor, David Wajc
Near-Optimum Online Ad Allocation for Targeted Advertising. EC (2015)
Joseph Naor, David Wajc
Near-Optimum Online Ad Allocation for Targeted Advertising. CoRR (2014)
Roee Engelberg, Alex Fabrikant, Michael Schapira, David Wajc
Best-response dynamics out of sync: complexity and characterization. EC (2013)
Andrzej Dudek, David Wajc
On the complexity of vertex-coloring edge-weightings. Discret. Math. Theor. Comput. Sci. 13 (3) (2011)