Source author record

David Wajc

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Information Theory math.IT Networking and Internet Architecture

Catalog footprint

Research overview

5works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Improved Online Contention Resolution for Matchings and Applications to the Gig Economy

Motivated by applications in the gig economy, we study approximation algorithms for a \emph{sequential pricing problem}. The input is a bipartite graph $G=(I,J,E)$ between individuals $I$ and jobs $J$ . The platform has a value of $v_j$ for matching job $j$ to an individual worker. In order to find a matching, the platform can consider the edges $(i j) \in E$ in any order and make a one-time take-it-or-leave-it offer of a price $π_{ij} = w$ of its choosing to $i$ for completing $j$ . The worker accepts the offer with a known probability $p_{ijw}$ ; in this case the job and the worker are irrevocably matched. What is the best way to make offers to maximize revenue and/or social welfare? The optimal algorithm is known to be NP-hard to compute (even if there is only a single job). With this in mind, we design efficient approximations to the optimal policy via a new Random-Order Online Contention Resolution Scheme (RO-OCRS) for matching. Our main result is a 0.456-balanced RO-OCRS in bipartite graphs and a 0.45-balanced RO-OCRS in general graphs. These algorithms improve on the recent bound of $\frac{1}{2}(1-e^{-2})\approx 0.432$ of [BGMS21], and improve on the best known lower bounds for the correlation gap of matching, despite applying to a significantly more restrictive setting. As a consequence of our OCRS results, we obtain a $0.456$ -approximate algorithm for the sequential pricing problem. We further extend our results to settings where workers can only be contacted a limited number of times, and show how to achieve improved results for this problem, via improved algorithms for the well-studied stochastic probing problem.

preprint2021arXiv

Streaming Submodular Matching Meets the Primal-Dual Method

We study streaming submodular maximization subject to matching/ $b$ -matching constraints (MSM/MSbM), and present improved upper and lower bounds for these problems. On the upper bounds front, we give primal-dual algorithms achieving the following approximation ratios. $\bullet$ $3+2\sqrt{2}\approx 5.828$ for monotone MSM, improving the previous best ratio of $7.75$ . $\bullet$ $4+3\sqrt{2}\approx 7.464$ for non-monotone MSM, improving the previous best ratio of $9.899$ . $\bullet$ $3+ε$ 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 $\frac{e}{e-1}\approx 1.582$ for MSM, and show ETH-based lower bounds of $\approx 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.

preprint2020arXiv

Network Coding Gaps for Completion Times of Multiple Unicasts

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 $\ell_p$ norm of completion times.

preprint2020arXiv

Rounding Dynamic Matchings Against an Adaptive Adversary

We present a new dynamic matching sparsification scheme. From this scheme we derive a framework for dynamically rounding fractional matchings against \emph{adaptive adversaries}. Plugging in known dynamic fractional matching algorithms into our framework, we obtain numerous randomized dynamic matching algorithms which work against adaptive adversaries (the first such algorithms, as all previous randomized algorithms for this problem assumed an \emph{oblivious} adversary). In particular, for any constant $ε>0$ , our framework yields $(2+ε)$ -approximate algorithms 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, with all these algorithms' guarantees holding against adaptive adversaries. All these results achieve \emph{polynomially} better update time to approximation tradeoffs than previously known to be achievable against adaptive adversaries.

preprint2015arXiv

Near-Optimum Online Ad Allocation for Targeted Advertising

Motivated by Internet targeted advertising, we address several ad allocation problems. Prior work has established these problems admit no randomized online algorithm better than $(1-\frac{1}{e})$ -competitive (\cite{karp1990optimal,mehta2007adwords}), yet simple heuristics have been observed to perform much better in practice. We explain this phenomenon by studying a generalization of the bounded-degree inputs considered by Buchbinder et al.~\cite{buchbinder2007online}, graphs which we call $(k,d)-bounded$ . In such graphs the maximal degree on the online side is at most $d$ and the minimal degree on the offline side is at least $k$ . We prove that for such graphs, these problems' natural greedy algorithms attain competitive ratio $1-\frac{d-1}{k+d-1}$ , tending to \emph{one} as $d/k$ tends to zero. We prove this bound is tight for these algorithms. Next, we develop deterministic primal-dual algorithms for the above problems achieving competitive ratio $1-(1-\frac{1}{d})^k>1-\frac{1}{e^{k/d}}$ , or \emph{exponentially} better loss as a function of $k/d$ , and strictly better than $1-\frac{1}{e}$ whenever $k\geq d$ . We complement our lower bounds with matching upper bounds for the vertex-weighted problem. Finally, we use our deterministic algorithms to prove by dual-fitting that simple randomized algorithms achieve the same bounds in expectation. Our algorithms and analysis differ from previous ad allocation algorithms, which largely scale bids based on the spent fraction of their bidder's budget, whereas we scale bids according to the number of times the bidder could have spent as much as her current bid. Our algorithms differ from previous online primal-dual algorithms, as they do not maintain dual feasibility, but only primal-to-dual ratio, and only attain dual feasibility upon termination. We believe our techniques could find applications to other well-behaved online packing problems.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.