Loading...
Please wait, while we are loading the content...
Similar Documents
Cility location and metric uncapacitated facility (2011).
| Content Provider | CiteSeerX |
|---|---|
| Author | Mohammad Hajiaghayi, T. Tiseanu, Scribe Catalin-Stefan |
| Abstract | Suppose we are given a graph G = (V, E), with a metric cost function c over the edges. (that is, a cost function which satisfies the triangle inequality). Suppose we have a set of clients D ⊆ V. Consider that facilities can be opened at any client vertex. Each client i ∈ D has an associated demand di. There are no facility opening costs. The task is to connect each client to a facility. Let us call this the connection cost. Additionally, all the opened facilities need to be connected to each other, via higher-cost edges. Let us call this second cost the Steiner cost. Let a set of facilities F ⊆ D be the set of opened facilities. Formally, we need to minimize the following objective function: Minimize ∑ j∈D dj · lc(i ∗ (j), j) + m · c(T) The first term in the objective function is the connection cost, and the second term is the Steiner cost. T is the Steiner tree used to connect the opened facilities. i ∗ (j) is the closest opened facility to client j ∈ D. lc(v, u) is the minimum distance between vertex v and u. Finally, each edge used in T costs |
| File Format | |
| Publisher Date | 2011-01-01 |
| Access Restriction | Open |
| Subject Keyword | Metric Uncapacitated Facility Cility Location Connection Cost Steiner Cost Opened Facility Higher-cost Edge Minimize Dj Lc Client Vertex Minimum Distance Triangle Inequality Cost Function First Term Second Term Steiner Tree Demand Di Second Cost Following Objective Function Facility Opening Cost Objective Function Metric Cost Function |
| Content Type | Text |
