Pith. sign in

REVIEW 1 cited by

Nearly Linear-Work Algorithms for Mixed Packing/Covering and Facility-Location Linear Programs

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

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

arxiv 1407.3015 v3 pith:7MCI5TOI submitted 2014-07-11 cs.DS

Neal E. Young This is my paper · ORCID
classification cs.DS
keywords algorithmsfacilitycoveringdescribeepsilonfirstlinearlocation
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

We describe the first nearly linear-time approximation algorithms for explicitly given mixed packing/covering linear programs, and for (non-metric) fractional facility location. We also describe the first parallel algorithms requiring only near-linear total work and finishing in polylog time. The algorithms compute $(1+\epsilon)$-approximate solutions in time (and work) $O^*(N/\epsilon^2)$, where $N$ is the number of non-zeros in the constraint matrix. For facility location, $N$ is the number of eligible client/facility pairs.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth

    cs.DS 2024-11 conditional novelty 8.0 of 10

    A nearly linear work, polylog depth parallel algorithm for approximating the Held-Karp bound and the k-ECSS LP, via a new core-sequence MWU framework.

Pith tools