Approximation algorithms for the bottleneck stretch factor problem
Assume that we are given the coordinates of \(n\) airports. Given an airplane that can fly a distance of \(b\) miles without refueling, a typical query is to determine the smallest value of \(t\) such that the airplane can travel between any pair of airports using flight segments of length at most \(b\) miles, such that the sum of the lengths of the flight segments is not longer than \(t\) times the direct ``as-the-crow-flies distance between the airports. This problem falls under the general category of \textit{bottleneck problems}. In our case, the \textit{stretch factor}, i.e., the value of \(t\), is a measure of the maximum increase in fuel costs caused by choosing a path other than the direct path between any source and any destination. (Clearly, this direct path cannot be taken if its length is larger than \(b\) miles.). For the entire collection see [Zbl 0958.00036].
- scientific article; zbMATH DE number 1809600
- A fast algorithm for a class of bottleneck problems
- Approximation algorithms for average stretch scheduling
- An approximation algorithm for a bottleneck traveling salesman problem
- An Approximation Algorithm for a Bottleneck Traveling Salesman Problem
- An algorithm for the bottleneck generalized assignment problem
- Approximations for a bottleneck Steiner tree problem
- Approximating the multi-level bottleneck assignment problem
- Approximating the multi-level bottleneck assignment problem
- Approximation algorithms for bounded facility location problems
This page was built for publication: Approximation algorithms for the bottleneck stretch factor problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2762528)
