𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Note on the algorithm for Johnson's single-route problem

✍ Scribed by B. I. Dushin

Publisher
Springer US
Year
1980
Tongue
English
Weight
276 KB
Volume
16
Category
Article
ISSN
1573-8337

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Approximation algorithms for the watchma
Approximation algorithms for the watchman route and zookeeper's problems
✍ Xuehou Tan πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 261 KB

Given a simple polygon P with n vertices and a starting point s on its boundary, the watchman route problem asks for a shortest route in P through s such that each point in the interior of the polygon can be seen from at least one point along the route. In this paper, we present a simple, linear-tim

A note on the greedy algorithm for the u
A note on the greedy algorithm for the unsplittable flow problem
✍ Petr Kolman πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 161 KB

In a recent paper Chekuri and Khanna improved the analysis of the greedy algorithm for the edge disjoint paths problem and proved the same bounds also for the related uniform capacity unsplittable flow problem. Here we show that their ideas can be used to get the same approximation ratio even for th

Two exact algorithms for the vehicle rou
Two exact algorithms for the vehicle routing problem on trees
✍ Pontien Mbaraga; AndrΓ© Langevin; Gilbert Laporte πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 80 KB πŸ‘ 2 views

This article describes a heuristic and two exact algorithms for several classes of vehicle routing problems defined on tree networks. These include capacitated and time-constrained vehicle routing problems. One of the exact algorithms is based on the computation of bin packing lower bounds. The othe