Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1090.90123
Lunday, Brian J.; Smith, J.Cole; Goldberg, Jeffrey B.
Algorithms for solving the conditional covering problem on paths. (English)
[J] Nav. Res. Logist. 52, No. 4, 293-301 (2005). ISSN 0894-069X; ISSN 1520-6750/e

Summary: Consider the conditional covering problem on an undirected graph, where each node represents a site that must be covered by a facility, and facilities may only be established at these nodes. Each facility can cover all sites that lie within some common covering radius, except the site at which it is located. Although this problem is difficult to solve on general graphs, there exist special structures on which the problem is easily solvable. In this paper, we consider the special case in which the graph is a simple path. For the case in which facility location costs do not vary based on the site, we derive characteristics of the problem that lead to a linear-time shortest path algorithm for solving the problem. When the facility location costs vary according to the site, we provide a more complex, but still polynomial-time, dynamic programming algorithm to find the optimal solution.

MSC 2000:: *90B80 Discrete location and assignment
90C39 Dynamic programming
90C59 Approximation methods and heuristics

Keywords: covering problems; location theory; dynamic programming

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]