Back to Search
Start Over
POLYNOMIAL TIME APPROXIMATION SCHEMES FOR THE TRAVELING REPAIRMAN AND OTHER MINIMUM LATENCY PROBLEMS.
- Source :
-
SIAM Journal on Computing . 2021, Vol. 50 Issue 5, p1580-1602. 23p. - Publication Year :
- 2021
-
Abstract
- We give a polynomial time approximation scheme for the weighted traveling re- pairman problem (TRP) in the Euclidean plane, on trees, and on planar graphs. This improves upon the quasi-polynomial time approximation schemes for the unweighted TRP in the Euclidean plane and trees and on the 3.59-approximation for planar graphs. The algorithms are based on a new decomposition technique that reduces the approximation of weighted TRP to instances for which we may restrict ourselves to solutions that are the concatenation of only a constant number of traveling salesman problem paths. A similar reduction applies to many other problems with an average completion time objective. To illustrate the strength of this approach, we apply the same technique to the well-studied scheduling problem of minimizing total weighted completion time under precedence constraints, 1/prec/∑wjCj, and present a polynomial time approximation scheme for the case of interval order precedence constraints. This improves on the known 3/2-approximation for this problem. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 50
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 153330904
- Full Text :
- https://doi.org/10.1137/19M126918X