A Minimax Facility Location Problem and the Cardinality Constrained Set Covering Problem.

Abstract

Given n demand points with weights (W sub i), an integer number k and a critical distance lambda, the problem discussed in the paper is one of choosing the location of k centers so that the total weight of demand points that lie within distance lambda from at least one center is maximized. This minimax location problem reduces to a cardinality constrained set covering problem (CCP), and for this latter problem a hybrid tree-search/dynamic programming algorithm is given. The dynamic program plays two roles: (1) it provides dominance tests to eliminate tree branchings and (2) the concavity properties associated with it can be used in a projection method to provide upper bounds for the nodes in the tree search.

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1975
Accession Number
ADA018113

Entities

People

  • Nicos Christofides

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Coverings
  • Dynamic Programming
  • Evolutionary Algorithms
  • Heuristic Methods
  • Mathematics

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Systems Analysis and Design