Text

Approximating Min-Mean-Cycle for Low-Diameter Graphs in Near-Optimal Time and Memory

We revisit Min-Mean-Cycle, the classical problem of finding a cycle in a weighted directed graph with minimum mean weight. Despite an extensive algorithmic literature, previous work failed to achieve a near-linear runtime in the number of edges m. We propose an algorithm with near-linear runtime O~(m(Wmax/ϵ)2) for computing an ϵ additive approximation on graphs with polylogarithmic diameter and weights of magnitude at most Wmax. In particular, this is the first algorithm whose runtime scales in the number of vertices n as O~(n2) for the complete graph. Moreover---unconditionally on the diameter---the algorithm uses only O(n) memory beyond reading the input, making it “memory-optimal". Our approach is based on solving a linear programming (LP) relaxation using entropic regularization, which reduces the LP to a Matrix Balancing problem---à la the popular reduction of Optimal Transport to Matrix Scaling. We then round the fractional LP solution using a variant of the classical Cycle-Canceling algorithm that is sped up to near-linear runtime at the expense of being approximate, and implemented in a memory-optimal manner. The algorithm is simple to implement and is competitive with the state-of-the-art methods in practice.

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON OPTIMIZATION; Vol.32 No.3 July-September 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1791-1816

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

APPROXIMATION ALGORITHM
LINEAR PROGRAMMING RELAXATION
ENTROPIC REGULARIZATION
MIN-MEAN-CYCLE
NEAR-LINEAR RUNTIME
MATRIX BALANCING

Info Detail Spesifik

https://doi.org/10.1137/21M1439390

Pernyataan Tanggungjawab

Jason M. Altschuler, Pablo A. Parrilo

Versi lain/terkait

Lampiran Berkas

Komentar