The K-connection location problem in a plane

Simin Huang, Rajan Batta, Kathrin Klamroth, Rakesh Nagi

Research output: Contribution to journalArticlepeer-review


This paper determines the optimal location of K connections in the plane, where a connection links pairs of existing facilities. Both uncapacitated and capacitated versions of the problem are considered. Discretization results for general polyhedral gauges and other properties are established. Two heuristic algorithms are developed for each case using the concept of a shortest path flow set coupled with a sequential location and allocation approach. Computational results show that the algorithms are efficient and accurate.

Original languageEnglish (US)
Pages (from-to)193-209
Number of pages17
JournalAnnals of Operations Research
Issue number1
StatePublished - Jan 2005
Externally publishedYes


  • Capacity
  • Connection
  • Planar location

ASJC Scopus subject areas

  • Decision Sciences(all)
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'The K-connection location problem in a plane'. Together they form a unique fingerprint.

Cite this