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 Tools annual

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 monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We present an interior point method for the min-cost flow problem that usesarc contractions and deletions to steer clear from the boundary of the polytopewhen path-following methods come too close. We obtain a randomized algorithmrunning in expected $\tilde O( m^{3/2} )$ time that only visits integer latticepoints in the vicinity of the central path of the polytope. This enables us touse integer arithmetic like classical combinatorial algorithms typically do. Weprovide explicit bounds on the size of the numbers that appear during allcomputations. By presenting an integer arithmetic interior point algorithm weavoid the tediousness of floating point error analysis and achieve a methodthat is guaranteed to be free of any numerical issues. We thereby eliminate oneof the drawbacks of numerical methods in contrast to combinatorial min-costflow algorithms that still yield the most efficient implementations inpractice, despite their inferior worst-case time complexity.

An Integer Interior Point Method for Min-Cost Flow Using Arc Contractions and Deletions