REVIEW 1 cited by
Lipschitz Continuous Algorithms for Covering Problems
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Lipschitz Continuous Algorithms for Covering Problems
read the original abstract
Combinatorial algorithms are widely used for decision-making and knowledge discovery, and it is important to ensure that their output remains stable even when subjected to small perturbations in the input. Failure to do so can lead to several problems, including costly decisions, reduced user trust, potential security concerns, and lack of replicability. Unfortunately, many fundamental combinatorial algorithms are vulnerable to small input perturbations. To address the impact of input perturbations on algorithms for weighted graph problems, Kumabe and Yoshida (FOCS'23) recently introduced the concept of Lipschitz continuity of algorithms. This work explores this approach and designs Lipschitz continuous algorithms for covering problems, such as the minimum vertex cover, set cover, and feedback vertex set problems. Our algorithm for the feedback vertex set problem is based on linear programming, and in the rounding process, we develop and use a technique called cycle sparsification, which may be of independent interest.
Forward citations
Cited by 1 Pith paper
-
Differentiable Approximations for Distance Queries
A (1+ε)-approximate Euclidean distance function that is differentiable and returns gradients, using O(n/ε^(d/2)) space and O(log(n/ε)) query time.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.