English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We consider the stochastic matching problem. An edge-weighted general (i.e., not necessarily bipartite) graph G(V, E) is given in the input, where each edge in E is realized independently with probability p ; the realization is initially unknown, however, we are able to query the edges to determine whether they are realized. The goal is to query only a small number of edges to find a realized matching that is sufficiently close to the maximum matching among all realized edges. The stochastic matching problem has received a considerable attention during the past decade after the initial paper of Chen et al. [ICALP'09] because of its numerous real-world applications in kidney-exchange, matchmaking services, online labor markets, and advertisements. Most relevant to our work are the recent papers of Blum et al. [EC'15], Assadi et al. [EC'16, EC'17] and Maehara and Yamaguchi~[SODA'18] that consider the same model of stochastic matching. Our main result is an adaptive algorithm that for any arbitrarily small ε > 0, finds a (1-ε)-approximation in expectation, by querying only O(1) edges per vertex. We further show that our approach leads to a (1/2-ε)-approximate non-adaptive algorithm that also uses $O(1)$ edges per vertex. Prior to our work, no nontrivial approximation was known for weighted graphs using a constant per-vertex budget. The state-of-the-art adaptive (resp. non-adaptive) algorithm of Maehara and Yamaguchi achieves a (1-ε)-approximation (resp. (1/2-ε)-approximation) by querying up to O(w łogn) edges per vertex where w denotes the maximum integer edge-weight. Our result is a substantial improvement over this bound and has an appealing message: No matter what the structure of the input graph is, one can get arbitrarily close to the optimum solution by querying only a constant number of edges per vertex. To obtain our results, we introduce novel properties of a generalization of augmenting paths to weighted matchings that may be of independent interest.

Almost Optimal Stochastic Weighted Matching with Few Queries