[2209.07520] On (Random-order) Online Contention Resolution Schemes for the Matc...
source link: https://arxiv.org/abs/2209.07520
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Data Structures and Algorithms
[Submitted on 15 Sep 2022]
On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
We present new results for online contention resolution schemes for the matching polytope of graphs, in the random-order (RCRS) and adversarial (OCRS) arrival models. Our results include improved selectability guarantees (i.e., lower bounds), as well as new impossibility results (i.e., upper bounds). By well-known reductions to the prophet (secretary) matching problem, a c-selectable OCRS (RCRS) implies a c-competitive algorithm for adversarial (random order) edge arrivals. Similar reductions are also known for the query-commit matching problem. For the adversarial arrival model, we present a new analysis of the OCRS of Ezra et al.~(EC, 2020). We show that this scheme is 0.344-selectable for general graphs and 0.349-selectable for bipartite graphs, improving on the previous 0.337 selectability result for this algorithm. We also show that the selectability of this scheme cannot be greater than 0.361 for general graphs and 0.382 for bipartite graphs. We further show that no OCRS can achieve a selectability greater than 0.4 for general graphs, and 0.433 for bipartite graphs.
For random-order arrivals, we present two attenuation-based schemes which use new attenuation functions. Our first RCRS is 0.474-selectable for general graphs, and our second is 0.476-selectable for bipartite graphs. These results improve upon the recent 0.45 (and 0.456) selectability results for general graphs (respectively, bipartite graphs) due to Pollner et al.~(EC, 2022). On general graphs, our 0.474-selectable RCRS provides the best known positive result even for offline contention resolution, and also for the correlation gap. We conclude by proving a fundamental upper bound of 0.5 on the selectability of RCRS, using bipartite graphs.
| Subjects: | Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Combinatorics (math.CO) |
| ACM classes: | F.2.2; G.2.2 |
| Cite as: | arXiv:2209.07520 [cs.DS] |
| (or arXiv:2209.07520v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2209.07520 |
Recommend
-
31
Side channel attacks such as Spectre or Meltdown allow data leakage from an unwilling process. Until now, transient execution side channel attacks primarily leveraged cache-based side channels to leak information. The ver...
-
21
The JVM’s garbage collectors make use of Thread-Local Allocation Buffers (TLABs) to improve allocation performance. In this article we’re going to understand what TLABs are, how they affect the code generated by the JIT for allocation and what t...
-
18
lck hang和enq: IV – contention的问题处理 版权声明：本文为Buddy Yuan原创文章，转载请注明出处。原文地址：
-
7
Windows 10 poor performance compared to Windows 7 (page fault handling is not scalable, severe lock contention when no of threads > 16)We set up two identical HP Z840 Workstations with the following specs 2 x Xeon E5-2690 v4 @...
-
7
How to optimize ORDER BY RANDOM() 2021-05-07 Database Optimization Series: This article is part of a series that helps developers optimize their database queries. I...
-
14
Get Data in Random Order From an ACF Repeater Field ...
-
3
Measuring Lock Contention When naively profiling multi-threaded applications the time spent waiting for mutexes is not necessar...
-
7
The 10 Best Online Random Number Generators By Jack Ryan Published 23 minutes ago If you need to make a quick, random decisio...
-
4
Sample and obtain the results in random order 1...
-
8
Solving Major Database Contention Problems with Throttling and Akka.NET Streams Alleviate strain on production systems with in-process Akka.NET s...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK