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

Graph algorithms are widely used for decision making and knowledge discovery.To ensure their effectiveness, it is essential that their output remains stableeven when subjected to small perturbations to the input because frequent outputchanges can result in costly decisions, reduced user trust, potential securityconcerns, and lack of replicability. In this study, we consider the Lipschitzcontinuity of algorithms as a stability measure and initiate a systematic studyof the Lipschitz continuity of algorithms for (weighted) graph problems.  Depending on how we embed the output solution to a metric space, we can thinkof several Lipschitzness notions. We mainly consider the one that is invariantunder scaling of weights, and we provide Lipschitz continuous algorithms andlower bounds for the minimum spanning tree problem, the shortest path problem,and the maximum weight matching problem. In particular, our shortest pathalgorithm is obtained by first designing an algorithm for unweighted graphsthat are robust against edge contractions and then applying it to theunweighted graph constructed from the original weighted graph.  Then, we consider another Lipschitzness notion induced by a natural mappingthat maps the output solution to its characteristic vector. It turns out thatno Lipschitz continuous algorithm exists for this Lipschitz notion, and weinstead design algorithms with bounded pointwise Lipschitz constants for theminimum spanning tree problem and the maximum weight bipartite matchingproblem. Our algorithm for the latter problem is based on an LP relaxation withentropy regularization.

Lipschitz Continuous Algorithms for Graph Problems