An official website of the United States government
One of the most basic problems in dynamic graph algorithms is to maintain a maximal matching as edges are inserted and deleted over time. In a line of work started by Baswana, Gupta and Sen, and then completed by Solomon, it was shown how to solve this problem in amortized expected time $O(1)$ per update. (Interestingly, achieving worst-case expected $O(1)$ remains open.) Recent work by Behnezhad et al.~suggests that very simple alternative algorithm may also perform well: simply maintain a randomized greedy matching. They show that this solution can be used to achieve $$O(\log^4 n)$$ expected time per update. In this paper, we show that the randomized greedy solution is even much more efficient than Behnezhad et al.'s result might seem to suggest, achieving an expected time bound of $$O((\log \log n)^2)$$ per update. This new bound is within a quadratic factor of tight, since one of the $$\log \log n$$ factors unavoidably comes from the algorithm's use of Van Emde Boas trees. Our result comes with several consequences. We obtain a nearly exponential time improvement for the problem of maintaining a history-independent dynamic maximal matching; a nearly exponential time improvement for the problem of maintaining a dynamic maximal matching with \emph{worst-case} expected time guarantees; and a polynomial improvement for the problem of maintaining a dynamic maximal matching with \emph{high-probability} time guarantees. Our result on history independence is of special interest given the major push in the data-structures community in recent years to study history independence as a privacy guarantee for data structures.
more »
« less
This content will become publicly available on June 9, 2027
Greedy Open Addressing Revisited: Beyond Yao’s Lower Bound
In a widely-cited 1985 result, Yao showed that any greedy open-addressed hash table, when filled to $$1 - \epsilon$$ full, must incur an amortized expected query time of at least $$\Omega(\log \epsilon^{-1})$$. To overcome this lower bound, prior work has focused on modifying the setup of the insertion algorithm, by either reordering items or placing items non-greedily. We show that, in fact, no such modifications are necessary: by simply decoupling the greedy query algorithm from the greedy insertion algorithm, it is possible to get an amortized expected query time of $O(1).$ The same relaxation also lets us bypass a barrier for worst-case expected query time, bringing the bound down to $$O(\log \epsilon^{-1})$$. Finally, we show how to achieve both of these query bounds while also achieving near-optimal insertion times, for both solutions that do and solutions that do not know the parameter $$\epsilon$$ beforehand.
more »
« less
- Award ID(s):
- 2504471
- PAR ID:
- 10698362
- Publisher / Repository:
- ACM
- Date Published:
- ISBN:
- 9798400725364
- Page Range / eLocation ID:
- 1116 to 1127
- Format(s):
- Medium: X
- Location:
- Salt Lake City UT USA
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider the problem of estimating the spectral density of the normalized adjacency matrix of an $$n$$-node undirected graph. We provide a randomized algorithm that, with $$O(n\epsilon^{-2})$$ queries to a degree and neighbor oracle and in $$O(n\epsilon^{-3})$$ time, estimates the spectrum up to $$\epsilon$$ accuracy in the Wasserstein-1 metric. This improves on previous state-of-the-art methods, including an $$O(n\epsilon^{-7})$$ time algorithm from [Braverman et al., STOC 2022] and, for sufficiently small $$\epsilon$$, a $$2^{O(\epsilon^{-1})}$$ time method from [Cohen-Steiner et al., KDD 2018]. To achieve this result, we introduce a new notion of graph sparsification, which we call \emph{nuclear sparsification}. We provide an $$O(n\epsilon^{-2})$$-query and $$O(n\epsilon^{-2})$$-time algorithm for computing $$O(n\epsilon^{-2})$$-sparse nuclear sparsifiers. We show that this bound is optimal in both its sparsity and query complexity, and we separate our results from the related notion of additive spectral sparsification. Of independent interest, we show that our sparsification method also yields the first \emph{deterministic} algorithm for spectral density estimation that scales linearly with $$n$$ (sublinear in the representation size of the graph).more » « less
-
For any forest G = (V, E) it is possible to orient the edges E so that no vertex in V has out-degree greater than 1. This paper considers the incremental edge-orientation problem, in which the edges E arrive over time and the algorithm must maintain a low-out-degree edge orientation at all times. We give an algorithm that maintains a maximum out-degree of 3 while flipping at most O(log log n) edge orientations per edge insertion, with high probability in n. The algorithm requires worst-case time O(log n log log n) per insertion, and takes amortized time O(1). The previous state of the art required up to O(log n/ log log n) edge flips per insertion. We then apply our edge-orientation results to the problem of dynamic Cuckoo hashing. The problem of designing simple families H of hash functions that are compatible with Cuckoo hashing has received extensive attention. These families H are known to satisfy static guarantees, but do not come typically with dynamic guarantees for the running time of inserts and deletes. We show how to transform static guarantees (for 1-associativity) into near-state-of-the-art dynamic guarantees (for O(1)-associativity) in a black-box fashion. Rather than relying on the family H to supply randomness, as in past work, we instead rely on randomness within our table-maintenance algorithm.more » « less
-
We consider the allocation problem in which $$m \leq (1-\epsilon) dn $$ items are to be allocated to $$n$$ bins with capacity $$d$$. The items $$x_1,x_2,\ldots,x_m$$ arrive sequentially and when item $$x_i$$ arrives it is given two possible bin locations $$p_i=h_1(x_i),q_i=h_2(x_i)$$ via hash functions $$h_1,h_2$$. We consider a random walk procedure for inserting items and show that the expected time insertion time is constant provided $$\epsilon = \Omega\left(\sqrt{ \frac{ \log d}{d}} \right).$$more » « less
-
Given a set $$P$$ of $$n$$ points in the plane, we consider the problem of computing the number of points of $$P$$ in a query unit disk (i.e., all query disks have the same radius). We show that the main techniques for simplex range searching in the plane can be adapted to this problem. For example, by adapting Matoušek's results, we can build a data structure of $O(n)$ space in $$O(n^{1+\delta})$$ time (for any $$\delta>0$$) so that each query can be answered in $$O(\sqrt{n})$$ time; alternatively, we can build a data structure of $$O(n^2/\log^2 n)$$ space with $$O(n^{1+\delta})$$ preprocessing time (for any $$\delta>0$$) and $$O(\log n)$$ query time. Our techniques lead to improvements for several other classical problems in computational geometry. 1. Given a set of $$n$$ unit disks and a set of $$n$$ points in the plane, the batched unit-disk range counting problem is to compute for each disk the number of points in it. Previous work [Katz and Sharir, 1997] solved the problem in $$O(n^{4/3}\log n)$$ time. We give a new algorithm of $$O(n^{4/3})$$ time, which is optimal as it matches an $$\Omega(n^{4/3})$$-time lower bound. For small $$\chi$$, where $$\chi$$ is the number of pairs of unit disks that intersect, we further improve the algorithm to $$O(n^{2/3}\chi^{1/3}+n^{1+\delta})$$ time, for any $$\delta>0$$. 2. The above result immediately leads to an $$O(n^{4/3})$$ time optimal algorithm for counting the intersecting pairs of circles for a set of $$n$$ unit circles in the plane. The previous best algorithms solve the problem in $$O(n^{4/3}\log n)$$ deterministic time [Katz and Sharir, 1997] or in $$O(n^{4/3}\log^{2/3} n)$$ expected time by a randomized algorithm [Agarwal, Pellegrini, and Sharir, 1993]. 3. Given a set $$P$$ of $$n$$ points in the plane and an integer $$k$$, the distance selection problem is to find the $$k$$-th smallest distance among all pairwise distances of $$P$$. The problem can be solved in $$O(n^{4/3}\log^2 n)$$ deterministic time [Katz and Sharir, 1997] or in $$O(n\log n+n^{2/3}k^{1/3}\log^{5/3}n)$$ expected time by a randomized algorithm [Chan, 2001]. Our new randomized algorithm runs in $$O(n\log n +n^{2/3}k^{1/3}\log n)$$ expected time. 4. Given a set $$P$$ of $$n$$ points in the plane, the discrete $$2$$-center problem is to compute two smallest congruent disks whose centers are in $$P$$ and whose union covers $$P$$. An $$O(n^{4/3}\log^5 n)$$-time algorithm was known [Agarwal, Sharir, and Welzl, 1998]. Our techniques yield a deterministic algorithm of $$O(n^{4/3}\log^{10/3} n\cdot (\log\log n)^{O(1)})$$ time and a randomized algorithm of $$O(n^{4/3}\log^3 n\cdot (\log\log n)^{1/3})$$ expected time.more » « less
