Record number :
Title of article :
2-InterConnected Facility Location: Specification, Complexity, and Exact Solutions
Author/Authors :
C.M. Chimani، نويسنده , , Markus and Kandyba، نويسنده , , Maria and Martens، نويسنده , , Maren، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2013
Pages :
From page :
To page :
Abstract :
Connected facility location combines cost-efficient facility placement and the requirement to connect the facilities among each other. Such problems arise, e.g., in telecommunication applications where networks consist of a central core and local clients connected to it. Reliability of the core is a central issue, and we may hence require the core to be at least 2-connected. ablish the problem class of 2-interConnected Facility Location (2-iCFL), categorize its central variants, and prove that they are hard to approximate. However, our computational results show that our orientation-based ILPs allow us to effectively solve such problems to optimality for hundreds of nodes. We also establish constructive characterizations for feasible problem instances, to be used for algorithmic feasibility checks, preprocessing, and heuristics.
Keywords :
Facility location , 2-connectivity , inapproximability , Exact algorithms , integer programming , EXPERIMENTS
Journal title :
Electronic Notes in Discrete Mathematics
Serial Year :
Link To Document :