We study the approximate maximum weight matching (MWM) problem in a fully dynamic graph subject to edge insertions and deletions. We design meta-algorithms that reduce the problem to the unweighted approximate maximum cardinality matching (MCM) problem. Despite recent progress on bipartite graphs – Bernstein-Dudeja-Langley (STOC 2021) and Bernstein-Chen-Dudeja-Langley-Sidford-Tu (SODA 2025) – the only previous meta-algorithm that applied to non-bipartite graphs suffered a \(\frac12\) approximation loss (Stubbs-Williams, ITCS 2017). We significantly close the weighted-and-unweighted gap by showing the first low-loss reduction that transforms any fully dynamic \((1-\varepsilon)\)-approximate MCM algorithm on bipartite graphs into afully dynamic \((1-\varepsilon)\)–approximate MWM algorithm on general (not necessarily bipartite) graphs, with only a \(\operatorname{poly}(\log n/\varepsilon)\) overhead in the update time. Central to our approach is a new primal–dual framework that reduces the computation of an approximate MWM in general graphs to a sequence of approximate induced matching queries on an auxiliary bipartite extension. In addition, we give the first conditional lower bound on approximate partially dynamic matching with worst-case update time.

In several two-sided markets, including labor and dating, agents typically have limited information about their preferences prior to mutual interactions. This issue can result in matching frictions, as arising in the labor market for medical residencies, where high application rates are followed by a large number of interviews. Yet, the extensive literature on two-sided matching primarily focuses on models where agents know their preferences, leaving the interactions necessary for preference discovery largely overlooked. This paper studies this problem using an algorithmic approach, extending Gale-Shapley’s deferred acceptance to this context. Two algorithms are proposed. The first is an adaptive algorithm that expands upon Gale-Shapley’s deferred acceptance by incorporating interviews between applicants and positions. Similar to deferred acceptance, one side sequentially proposes to the other. However, the order of proposals is carefully chosen to ensure an interim stable matching is found. Furthermore, with high probability, the number of interviews conducted by each applicant or position is limited to O(log² n). In many seasonal markets, interactions occur more simultaneously, consisting of an initial interview phase followed by a clearing stage. We present a non-adaptive algorithm for generating a single stage set of in tiered random markets. The algorithm finds an interim stable matching in such markets while assigning no more than O(log³ n) interviews to each applicant or position.

We provide an algorithm that maintains, against an adaptive adversary, a (1 — ε )-approximate maximum matching in n-node m-edge general (not necessarily bipartite) undirected graph undergoing edge deletions with high probability with (amortized) O (poly(ε-1, log n )) time per update. We also obtain the same update time for maintaining a fractional approximate weighted matching (and hence an approximation to the value of the maximum weight matching) and an integral approximate weighted matching in dense graphs.1 Our unweighted result improves upon the prior state-of-the-art which includes a poly(log n ) · 2O (1/ɛ2) update time [Assadi-Bernstein-Dudeja 2022] and an update time [Gupta-Peng 2013], and our weighted result improves upon the log n ) update time due to [Gupta-Peng 2013].

We consider the foundational problem of maintaining a (1 — ε )-approximate maximum weight matching (MWM) in an n-node dynamic graph undergoing edge insertions and deletions. We provide a general reduction that reduces the problem on graphs with a weight range of poly(n ) to poly(1/ε ) at the cost of just an additive poly(1/ε ) in update time. This improves upon the prior reduction of Gupta-Peng (FOCS 2013) which reduces the problem to a weight range of ε-O (1/ε) with a multiplicative cost of O (log n ).

High-accuracy real-time data stream estimations are critical for various applications, and sliding-window-based techniques have attracted wide attention. However, existing solutions struggle to achieve high accuracy, generality, and low memory usage simultaneously. To overcome these limitations, we present MicroscopeSketch, a high-accuracy sketch framework. Our key technique, called adaptive zooming, dynamically adjusts the granularity of counters to maximize accuracy while minimizing memory usage. By applying MicroscopeSketch to three specific tasks---frequency estimation, top-k frequent items discovery, and top-k heavy changes identification-we demonstrate substantial improvements over existing methods, reducing errors by roughly 4 times for frequency estimation and 3 times for identifying top-k items. The relevant source code is available in a GitHub repository.