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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper, we study a set of combinatorial optimization problems onweighted graphs: the shortest path problem with negative weights, the weightedperfect bipartite matching problem, the unit-capacity minimum-cost maximum flowproblem and the weighted perfect bipartite $b$-matching problem under theassumption that $\Vert b\Vert_1=O(m)$. We show that each one of these fourproblems can be solved in $\tilde{O}(m^{10/7}\log W)$ time, where $W$ is theabsolute maximum weight of an edge in the graph, which gives the first in over25 years polynomial improvement in their sparse-graph time complexity.  At a high level, our algorithms build on the interior-point method-basedframework developed by Madry (FOCS 2013) for solving unit-capacity maximum flowproblem. We develop a refined way to analyze this framework, as well as providenew variants of the underlying preconditioning and perturbation techniques.Consequently, we are able to extend the whole interior-point method-basedapproach to make it applicable in the weighted graph regime.

Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in $\tilde{O}(m^{10/7} \log W)$ Time