When are NP-hard location problems easy? |
| |
| Authors: | Dorit S Hochbaum |
| |
| Institution: | (1) School of Business Administration, University of California, 350 Barrows Hall, 94720 Berkeley, California, USA |
| |
| Abstract: | We discuss in this paper several location problems for which it is an NP-hard problem to find an approximate solution. Given certain assumptions on the input distributions, we present polynomial algorithms that deliver a solution asymptotically close to the optimum with probability that is asymptotically one (the exact nature of this asymptotic convergence is described in the paper). In that sense the subproblems defined on the specified family of inputs are in fact easy.This research was supported in part by the National Science Foundation under grant ECS-8204695. |
| |
| Keywords: | Probabilistic analysis location problems heuristics NP-hard problems approximation algorithm asymptotic optimality |
| 本文献已被 SpringerLink 等数据库收录！ |
|
