Algorithms for solving the conditional covering problem on paths

Brian J. Lunday, J. Cole Smith, Jeffrey B. Goldberg

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)293-301
Number of pages9
JournalNaval Research Logistics
Volume52
Issue number4
DOIs
StatePublished - Jun 1 2005
Externally publishedYes

Keywords

  • Covering problems
  • Dynamic programming
  • Location theory

ASJC Scopus subject areas

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Algorithms for solving the conditional covering problem on paths'. Together they form a unique fingerprint.

  • Cite this