𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Restricted delivery problems on a network

✍ Scribed by Arkin, Esther M.; Hassin, Refael; Klein, Limor

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
125 KB
Volume
29
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

We consider a delivery problem on a network in which nodes have supplies or demands for certain products and arcs have lengths satisfying the triangle inequality. A vehicle of infinite capacity travels through the network, carrying products to their destinations, and is limited in that it can carry only a single type of product at a time. The general problem asks for a shortest delivery route of all products from their origin to their destination. Here, we consider certain restrictions on the delivery paths allowed and compare the quality of the solution of the unrestricted problem to that of the restricted one. Both the general and restricted problems are NP-hard, and we discuss approximation algorithms. We also give a constant factor approximation algorithm for the Clustered Traveling Salesman Problem. α­§ 1997

πŸ“œ SIMILAR VOLUMES

On capacitated stochastic chain problems
On capacitated stochastic chain problems in a network
✍ Ganapathy, L.; Nair, K. P. K. πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 110 KB

This paper considers two basic problems relating to capacitated chains in a stochastic network in which each arc has a discrete arbitrary probability distribution for its capacity. Given a sourcesink pair, the first problem is to find an optimal capacity chain subject to a chance constraint. By trea

A problem of restricted partitions
A problem of restricted partitions
✍ V. R. R. Uppuluri; J. A. Carpenter πŸ“‚ Article πŸ“… 1974 πŸ› John Wiley and Sons 🌐 English βš– 186 KB
Solution of a restricted Hadamard proble
Solution of a restricted Hadamard problem on Minkowski spaces
✍ Yuri Yu. Berest πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 281 KB πŸ‘ 1 views

We give a complete solution of Hadamard's problem concerning Huygens' principle on evendimensional Minkowski spaces M n+1 for a restricted class of linear, second-order, normal hyperbolic operators L = n+1 +u(x 1 , x 2 ) with real (locally) analytic potentials u = u(x 1 , x 2 ) depending on two spat

Solving min-max shortest-path problems o
Solving min-max shortest-path problems on a network
✍ Ishwar Murthy; Shenq-Shyong Her πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 877 KB

In this article we consider the problem of determining a path between two nodes in a network that minimizes the maximum of r path length values associated with it. This problem has a direct application in scheduling. It also has indirect applications in a class of routing problems and when consideri

A problem on blocking probabilities in c
A problem on blocking probabilities in connecting networks
✍ F. R. K. Chung; F. K. Hwang πŸ“‚ Article πŸ“… 1977 πŸ› John Wiley and Sons 🌐 English βš– 286 KB

## Abstract We begin with a three‐stage linear graph in which the first stage has a single node u and the third stage a single node v. The second stage has k independent nodes, each of which is connected by one link to u and to v. In general, we can form a (2n+1)‐stage linear graph recursively by l