Arrow Research search

Author name cluster

David Wajc

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

18 papers
2 author rows

Possible papers

18

FOCS Conference 2025 Conference Paper

Online Edge Coloring: Sharp Thresholds

  • Joakim Blikstad
  • Ola Svensson
  • Radu Vintan
  • David Wajc

Vizing’s theorem guarantees that every graph with maximum degree $\Delta$ admits an edge coloring using $\Delta+1$ colors. In online settings-where edges arrive one at a time and must be colored immediately-a simple greedy algorithm uses at most $2 \Delta-1$ colors. Over thirty years ago, Bar-Noy, Motwani, and Naor [IPL’92] proved that this guarantee is optimal among deterministic algorithms when $\Delta=O(\log n)$, and among randomized algorithms when $\Delta=O(\sqrt{\log n})$. While deterministic improvements seemed out of reach, they conjectured that for graphs with $\Delta=\omega(\log n)$, randomized algorithms can achieve $(1+o(1)) \Delta$ edge coloring. This conjecture was recently resolved in the affirmative: a $(1+o(1)) \Delta$ coloring is achievable online using randomization for all graphs with $\Delta=\omega(\log n)$ [BSVW STOC’24]. Our results go further, uncovering two findings not predicted by the original conjecture. First, we give a deterministic online algorithm achieving $(1+o(1)) \Delta$-colorings for all $\Delta=\omega(\log n)$. Second, we give a randomized algorithm achieving $(1+o(1)) \Delta$ colorings already when $\Delta=\omega(\sqrt{\log n})$. Our results establish sharp thresholds for when greedy can be surpassed, and nearoptimal guarantees can be achieved - matching the impossibility results of [BNMN IPL’92], both deterministically and randomly.

Details

STOC Conference 2024 Conference Paper

Online Edge Coloring Is (Nearly) as Easy as Offline

  • Joakim Blikstad
  • Ola Svensson
  • Radu Vintan
  • David Wajc

The classic theorem of Vizing (Diskret. Analiz.’64) asserts that any graph of maximum degree Δ can be edge colored (offline) using no more than Δ+1 colors (with Δ being a trivial lower bound). In the online setting, Bar-Noy, Motwani and Naor (IPL’92) conjectured that a (1+ o (1))Δ-edge-coloring can be computed online in n -vertex graphs of maximum degree Δ=ω(log n ). Numerous algorithms made progress on this question, using a higher number of colors or assuming restricted arrival models, such as random-order edge arrivals or vertex arrivals (e.g., AGKM FOCS’03, BMM SODA’10, CPW FOCS’19, BGW SODA’21, KLSST STOC’22). In this work, we resolve this longstanding conjecture in the affirmative in the most general setting of adversarial edge arrivals. We further generalize this result to obtain online counterparts of the list edge coloring result of Kahn (J. Comb. Theory. A’96) and of the recent “local” edge coloring result of Christiansen (STOC’23).

Details

SODA Conference 2023 Conference Paper

Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time

  • Sayan Bhattacharya
  • Peter Kiss
  • Thatchaphol Saranurak
  • David Wajc

We present dynamic algorithms with polylogarithmic update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximation ratio strictly better than 2. Specifically, we obtain a approximation in bipartite graphs and a 1. 973 + ε approximation in general graphs. We thus answer in the affirmative the value version of the major open question repeatedly asked in the dynamic graph algorithms literature. Our randomized algorithms' approximation and worst-case update time bounds both hold w. h. p. against adaptive adversaries. Our algorithms are based on simulating new two-pass streaming matching algorithms in the dynamic setting. Our key new idea is to invoke the recent sublinear-time matching algorithm of Behnezhad (FOCS'21) in a white-box manner to efficiently simulate the second pass of our streaming algorithms, while bypassing the well-known vertex-update barrier.

Details

SODA Conference 2021 Conference Paper

Online Edge Coloring Algorithms via the Nibble Method

  • Sayan Bhattacharya
  • Fabrizio Grandoni 0001
  • David Wajc

Nearly thirty years ago, Bar-Noy, Motwani and Naor [IPL'92] conjectured that an online (1 + o (1))Δ-edge-coloring algorithm exists for n -node graphs of maximum degree Δ = ω (log n ). This conjecture remains open in general, though it was recently proven for bipartite graphs under one-sided vertex arrivals by Cohen et al. [FOCS'19]. In a similar vein, we study edge coloring under widely-studied relaxations of the online model. Our main result is in the random-order online model. For this model, known results fall short of the Bar-Noy et al. conjecture, either in the degree bound [Aggarwal et al. FOCS'03], or number of colors used [Bahmani et al. SODA'10]. We achieve the best of both worlds, thus resolving the Bar-Noy et al. conjecture in the affirmative for this model. Our second result is in the adversarial online (and dynamic) model with recourse. A recent algorithm of Duan et al. [SODA'19] yields a (1 + ∊) Δ-edge-coloring with poly(log n/∊ ) recourse. We achieve the same with poly(1/ ∊ ) recourse, thus removing all dependence on n. Underlying our results is one common offline algorithm, which we show how to implement in these two online models. Our algorithm, based on the Rödl Nibble Method, is an adaptation of the distributed algorithm of Dubhashi et al. [TCS'98]. The Nibble Method has proven successful for distributed edge coloring. We display its usefulness in the context of online algorithms.

Details

SODA Conference 2021 Conference Paper

Streaming Submodular Matching Meets the Primal-Dual Method

  • Roie Levin
  • David Wajc

We study streaming submodular maximization subject to matching/ b -matching constraints (MSM/MS b M), and present improved upper and lower bounds for these problems. On the upper bounds front, we give primaldual algorithms achieving the following approximation ratios. for monotone MSM, improving the previous best ratio of 7. 75. for non-monotone MSM, improving the previous best ratio of 9. 899. for maximum weight b-matching, improving the previous best ratio of 4 + ∊. On the lower bounds front, we improve on the previous best lower bound of for MSM, and show ETH-based lower bounds of ≈ 1. 914 for polytime monotone MSM streaming algorithms. Our most substantial contributions are our algorithmic techniques. We show that the (randomized) primal-dual method, which originated in the study of maximum weight matching (MWM), is also useful in the context of MSM. To our knowledge, this is the first use of primal-dual based analysis for streaming submodular optimization. We also show how to reinterpret previous algorithms for MSM in our framework; hence, we hope our work is a step towards unifying old and new techniques for streaming submodular maximization, and that it paves the way for further new results.

Details

FOCS Conference 2020 Conference Paper

Network Coding Gaps for Completion Times of Multiple Unicasts

  • Bernhard Haeupler
  • David Wajc
  • Goran Zuzic

We study network coding gaps for the problem of makespan minimization of multiple unicasts. In this problem distinct packets at different nodes in a network need to be delivered to a destination specific to each packet, as fast as possible. The network coding gap specifies how much coding packets together in a network can help compared to the more natural approach of routing. While makespan minimization using routing has been intensely studied for the multiple unicasts problem, no bounds on network coding gaps for this problem are known. We develop new techniques which allow us to upper bound the network coding gap for the makespan of k unicasts, proving this gap is at most polylogarithmic in k. Complementing this result, we show there exist instances of k unicasts for which this coding gap is polylogarithmic in k. Our results also hold for average completion time, and more generally any lp norm of completion times.

Details

STOC Conference 2020 Conference Paper

Rounding dynamic matchings against an adaptive adversary

  • David Wajc

We present a new dynamic matching sparsification scheme. From this scheme we derive a framework for dynamically rounding fractional matchings against adaptive adversaries . Plugging in known dynamic fractional matching algorithms into our framework, we obtain numerous randomized dynamic matching algorithms which work against adaptive adversaries. In contrast, all previous randomized algorithms for this problem assumed a weaker, oblivious , adversary. Our dynamic algorithms against adaptive adversaries include, for any constant є >0, a (2+є)-approximate algorithm with constant update time or polylog worst-case update time, as well as (2−δ)-approximate algorithms in bipartite graphs with arbitrarily-small polynomial update time. All these results achieve polynomially better update time to approximation trade-offs than previously known to be achievable against adaptive adversaries.

Details

FOCS Conference 2019 Conference Paper

Online Matching with General Arrivals

  • Buddhima Gamlath
  • Michael Kapralov
  • Andreas Maggiori
  • Ola Svensson
  • David Wajc

The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomized algorithms for this setting. In comparison, more general arrival models, such as edge arrivals and general vertex arrivals, have proven more challenging and positive results are known only for various relaxations of the problem. In particular, even the basic question of whether randomization allows one to beat the trivially-optimal deterministic competitive ratio of 1/2 for either of these models was open. In this paper, we resolve this question for both these natural arrival models, and show the following. 1) For edge arrivals, randomization does not help - no randomized algorithm is better than 1/2 competitive. 2)For general vertex arrivals, randomization helps - there exists a randomized (1/2+Ω(1)) -competitive online matching algorithm.

Details

FOCS Conference 2019 Conference Paper

Tight Bounds for Online Edge Coloring

  • Ilan Reuven Cohen
  • Binghui Peng
  • David Wajc

Vizing's celebrated theorem asserts that any graph of maximum degree Δ admits an edge coloring using at most Δ+1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2Δ-1 colors, is optimal among online algorithms. Their lower bound has a caveat, however: it only applies to low-degree graphs, with Δ=O(log n), and they conjectured the existence of online algorithms using Δ(1+o(1)) colors for Δ=ω(log n). Progress towards resolving this conjecture was only made under stochastic arrivals (Aggarwal et al. , FOCS'03 and Bahmani et al. , SODA'10). We resolve the above conjecture for adversarial vertex arrivals in bipartite graphs, for which we present a (1+o(1))Δ-edge-coloring algorithm for Δ=ω(log n) known a priori. Surprisingly, if Δ is not known ahead of time, we show that no (e/(e-1) - Ω(1)) Δ-edge-coloring algorithm exists. We then provide an optimal, (e/(e-1)+o(1)) Δ-edge-coloring algorithm for unknown Δ=ω(log n). To obtain our results, we study a nonstandard fractional relaxation for edge coloring, for which we present optimal fractional online algorithms and a near-lossless online rounding scheme, yielding our optimal randomized algorithms.

Details

AAAI Conference 2018 Conference Paper

Approximation-Variance Tradeoffs in Facility Location Games

  • Ariel Procaccia
  • David Wajc
  • Hanrui Zhang

We revisit the well-studied problem of constructing strategyproof approximation mechanisms for facility location games, but offer a fundamentally new perspective by considering risk averse designers. Specifically, we are interested in the tradeoff between a randomized strategyproof mechanism’s approximation ratio, and its variance (which has long served as a proxy for risk). When there is just one facility, we observe that the social cost objective is trivial, and derive the optimal tradeoff with respect to the maximum cost objective. When there are multiple facilities, the main challenge is the social cost objective, and we establish a surprising impossibility result: under mild assumptions, no smooth approximation-variance tradeoff exists. We also discuss the implications of our work for computational mechanism design at large.

PDF Details

SODA Conference 2018 Conference Paper

Randomized Online Matching in Regular Graphs

  • Ilan Reuven Cohen
  • David Wajc

In this paper we study the classic online matching problem, introduced in the seminal work of Karp, Vazirani and Vazirani (STOC 1990), in regular graphs. For such graphs, an optimal deterministic algorithm as well as efficient algorithms under stochastic input assumptions were known. In this work, we present a novel randomized algorithm with competitive ratio tending to one on this family of graphs, under adversarial arrival order. Our main contribution is a novel algorithm which achieves competitive ratio in expectation on d -regular graphs. In contrast, we show that all previously-studied online algorithms have competitive ratio strictly bounded away from one. Moreover, we show the convergence rate of our algorithm's competitive ratio to one is nearly tight, as no algorithm achieves competitive ratio better than. Finally, we show that our algorithm yields a similar competitive ratio with high probability, as well as guaranteeing each vertex a probability of being matched tending to one.

Details