David Wajc

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