MTGZone
  • Communities
  • Create Post
  • heart
    Support Lemmy
  • search
    Search
  • Login
  • Sign Up
endofline@lemmy.ca to science@lemmy.worldEnglish · 3 months ago

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

arxiv.org

external-link
message-square
0
fedilink
3
external-link

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

arxiv.org

endofline@lemmy.ca to science@lemmy.worldEnglish · 3 months ago
message-square
0
fedilink
We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with $m$ edges and polynomially bounded integral demands, costs, and capacities in $m^{1+o(1)}$ time. Our algorithm builds the flow through a sequence of $m^{1+o(1)}$ approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized $m^{o(1)}$ time using a new dynamic graph data structure. Our framework extends to algorithms running in $m^{1+o(1)}$ time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, $p$-norm flows, and $p$-norm isotonic regression on arbitrary directed acyclic graphs.
alert-triangle
You must log in or register to comment.

science@lemmy.world

science@lemmy.world

Subscribe from Remote Instance

Create a post
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: !science@lemmy.world

A community to post scientific articles, news, and civil discussion.

rule #1: be kind

Visibility: Public
globe

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

  • 649 users / day
  • 1.59K users / week
  • 3.1K users / month
  • 9.98K users / 6 months
  • 6 local subscribers
  • 18.4K subscribers
  • 1.99K Posts
  • 18K Comments
  • Modlog
  • mods:
  • m3t00🌎@lemmy.world
  • Joleee@lemmy.world
  • laverabe@lemmy.world
  • DeadPand@midwest.social
  • laverabe@lemmy.zip
  • BE: 0.19.5
  • Modlog
  • Legal
  • Instances
  • Docs
  • Code
  • join-lemmy.org