lemmy.net.au
  • Communities
  • Create Post
  • Create Community
  • heart
    Support Lemmy
  • search
    Search
  • Login
  • Sign Up
RSS Bot@lemmy.bestiver.seMB to Hacker News@lemmy.bestiver.seEnglish · 7 days ago

Greedy is optimal for single-pass semi-streaming matching

arxiv.org

external-link
message-square
0
fedilink
1
external-link

Greedy is optimal for single-pass semi-streaming matching

arxiv.org

RSS Bot@lemmy.bestiver.seMB to Hacker News@lemmy.bestiver.seEnglish · 7 days ago
message-square
0
fedilink
Semi-Streaming Matching in a Single Pass II: Greedy is Optimal
arxiv.org
external-link
We prove that no single-pass semi-streaming algorithm (deterministic or randomized) can achieve a better-than-half approximation to the maximum matching problem. This implies the optimality of the naive greedy algorithm, answering an outstanding open question in the graph streaming literature since the introduction of the model over two decades ago. Our proof follows the "blueprint framework" introduced previously by the authors, which reduced proving lower bounds for semi-streaming matching to constructing certain combinatorial objects called blueprints. We present an optimal construction of blueprints that when used in this framework implies our semi-streaming matching lower bound. Our results also imply that the optimal competitive ratio of online matching with preemption is half, again matching the naive greedy algorithm, settling this open question as well.

Comments

alert-triangle
You must log in or register to comment.

Hacker News@lemmy.bestiver.se

hackernews@lemmy.bestiver.se

Subscribe from Remote Instance

You are not logged in. However you can subscribe from another Fediverse account, for example Lemmy or Mastodon. To do this, paste the following into the search field of your instance: !hackernews@lemmy.bestiver.se
lock
Community locked: only moderators can create posts. You can still comment on posts.

Posts from the RSS Feed of HackerNews.

The feed sometimes contains ads and posts that have been removed by the mod team at HN.

Source of the RSS Bot

Visibility: Public
globe

This community can be federated to other instances and be posted/commented in by their users.

  • 412 users / day
  • 1.74K users / week
  • 3.82K users / month
  • 6.67K users / 6 months
  • 1 local subscriber
  • 5.22K subscribers
  • 8.58K Posts
  • 5.57K Comments
  • Modlog
  • mods:
  • patrick@lemmy.bestiver.se
  • RSS Bot@lemmy.bestiver.se
  • BE: 0.19.9
  • Modlog
  • Instances
  • Docs
  • Code
  • join-lemmy.org