Source-linked AI summary
Buy-at-Bulk Facility Location on Trees
Shamisa Nematollahi, Daniel Vaz
TL;DR
The paper asks how buy-at-bulk facility location and cable-based capacity provisioning can be approximated on trees, especially when demands cannot be split across cables. It formalizes BBFL and kCFL variants and develops tree algorithms, obtaining PTAS results for splittable demands, hardness for cable-unsplittable demands, and exact-cost solutions with limited capacity violation.
Problem
The paper studies BBFL and kCFL on trees, including the new cable-unsplittable setting where each demand must use one cable per edge.
Method
The paper formalizes facility-location and buy-at-bulk network design together, then develops approximation and capacity-violating algorithms for splittable and cable-unsplittable tree instances.
Results
The paper gives PTASes for splittable BBFL and kCFL, proves 3/2−ε inapproximability for cable-unsplittable kCFL on stars, and gives a 2-approximation on trees.
Takeaways & Limitations
On trees, splittable demands admit near-optimal approximation, while cable-unsplittable demands permit optimal cost with 1+ε capacity violation and a 2-approximation without that guarantee.
Takeaways & Limitations
The splittable-demand structural lemma used by the paper does not hold for unsplittable demands.
Abstract
from arXiv · showhide
We consider the buy-at-bulk facility location problem (BBFL), a problem combining the classic facility location problem with buy-at-bulk network design, which finds motivation in telecommunication networks. In it, we are given a graph with edge lengths, opening costs and demands for each vertex, and a monotone and subadditive capacity-cost function, and our task is to open facilities on a subset of the vertices and route the demand from each vertex to these facilities. The cost of a solution (which we want to minimize) is given by the opening costs of the chosen facilities, plus the cost on each edge, which is given by its length times the cost of providing enough capacity for the demands through the edge, given by the capacity-cost function. A common variant of the problem, the $k$-cable facility location problem (kCFL), considers the case where capacity is provided by buying copies of given cable types, each with a certain capacity and cost. We study BBFL on tree instances and show, for the unit-demand and splittable variants, that the problem admits a PTAS (a $(1+ε)$-approximation for any $ε> 0$). We also consider kCFL in the new setting of cable-unsplittable demands, where the demand of a vertex cannot be split among multiple cables. We show that the problem is NP-hard to approximate to a factor better than $3/2$ on stars, and then provide an algorithm for tree instances that outputs a solution with optimal cost, but which exceeds the capacity on each cable by a factor of $1+ε$. As a consequence, we show that the problem has a $2$-approximation algorithm on trees.
1 Introduction
The paper studies buy-at-bulk facility location on trees, including splittable BBFL and kCFL and a novel cable-unsplittable kCFL variant. It establishes PTAS results, hardness on stars, and capacity-violating exact-cost and approximation algorithms.
- Problem setting: BBFL combines facility placement with network design, minimizing facility-opening costs and length-weighted capacity costs for routing vertex demands.Buy-at-bulk capacity costs are monotone and subadditive, so shared network trunks can reduce distribution costs.
- Problem setting: The kCFL variant supplies capacity by purchasing copies of k cable types, each with specified capacity and cost.For each edge, purchased cable copies must provide capacity at least equal to the routed demand.
- Splittable demands: A PTAS exists for BBFL on trees with splittable demands, and this implies a PTAS for splittable kCFL.The running times are f(ε) · poly(n) for BBFL and f(ε) · poly(n, k) for kCFL.
- Cable-unsplittable demands: Cable-unsplittable kCFL requires each demand to use a single cable on every edge, a setting motivated by indivisible packages or discrete containers.Repacking or splitting at intermediate nodes may be operationally expensive, technologically infeasible, or disallowed by design.
- Cable-unsplittable demands: 3/2−ε inapproximability holds for cable-unsplittable kCFL even on stars, while an exact-cost algorithm on trees permits capacity overload of at most 1+ε.The exact-cost algorithm runs in time n^k·f(ε), and the resulting tree algorithm gives a 2-approximation in time n^O(k).
2 Preliminaries
The preliminaries define BBFL and kCFL as facility-location problems with flow-based network capacity, then formalize cable-unsplittable routing and its relation to BBFL.
- Notation: The paper uses rooted-tree notation, directed arcs, indicator vectors, set-sums, and dominance to describe flows and dynamic-programming states.A cable (µ,c) dominates (µ′,c′) when it has at least as much capacity and no greater cost.
- Buy-at-bulk network design: Buy-at-bulk network design routes demands through graph edges whose costs equal edge length times a monotone, subadditive capacity-cost function.Subadditivity captures the economy of serving combined demand with one larger capacity rather than separate smaller capacities.
- BBFL: BBFL opens facilities at graph vertices and sends each vertex's demand by flow to the opened facilities while minimizing opening and edge costs.Its input includes edge lengths, facility-opening costs, vertex demands, and a monotone subadditive installation-cost function.
- kCFL: kCFL replaces the general capacity-cost function with bags of purchased cable copies whose total capacity covers each edge's flow.It is a special case of BBFL because cable-covering costs are monotone and subadditive.
- kCFL: For any ε > 0, a minimum-cost cable bag covering demand λ can be approximated within 1+ε in time polynomial in k and 1/ε.The algorithms do not require the usual economies-of-scale assumption for cable types.
- Cable-unsplittable variant: Cable-unsplittable kCFL assigns every vertex demand to one specific cable on each edge, with cables partitioned by flow direction.The paper identifies this as a new variant and notes that it does not easily reduce to BBFL.
3 Splittable-Demand BBFL
The section develops PTAS algorithms for splittable-demand BBFL on trees, using dynamic programming with rounded costs and non-dominated subtree states. The resulting algorithm achieves a (1 + ε)-approximation in polynomial time for fixed ε.
- 3 Splittable-Demand BBFL: A PTAS is given for splittable-demand BBFL on trees, extending the core approach from paths to tree instances.The path case provides a simpler introduction to the dynamic-programming ideas, while the tree algorithm assumes a binary tree after a cost-preserving transformation.
- Dynamic program: Non-dominated states are retained, eliminating states with no worse flow requirements and cost under the same flow direction.This pruning is applied after combining the facility-opening and no-facility cases.
- Dynamic program: The dynamic program stores pairs (λ, c), where c is the minimum subtree cost under a signed demand-flow constraint λ at the node boundary.Positive λ represents demand leaving toward the parent, while negative λ represents demand arriving from the parent.
- Approximation guarantee: (1 + ε)-approximation is obtained by rounding costs to multiples of ε·opt /n and optimizing the rounded instance with the dynamic program.The rounded-cost solution has original cost at most (1 + ε) opt.
- Dynamic program: At each internal node, the recurrence considers opening a facility or routing all local and child demand through the node toward its parent.The no-facility case conserves flow as λ = λ′ + λ′′ + d(v), while facility-opening states include the opening and connection costs.
- Approximation guarantee: O(ε−2 · poly(n)) running time follows because each state set has at most D = 2n/ε possible rounded cost values.The underlying dynamic-programming calculation is bounded using the number of retained cost values.
4 Cable-Unsplittable-Demand kCFL on Trees
The section studies cable-unsplittable-demand kCFL on trees, where demands cannot be split across cables. It establishes hardness on stars and uses resource augmentation to obtain optimal augmented-cost solutions and a 2-approximation for the original problem.
- Resource augmentation: The algorithm solves a resource-augmented variant allowing each cable to carry up to (1 + ε) times its nominal capacity.Flows assigned to the same cable must remain in one direction, while the optimum solution used for comparison respects the original capacities.
- Hardness: Cable-unsplittable kCFL is APX-hard even on stars with one cable type.In particular, it is NP-hard to approximate the problem within 3/2 − ε for any ε > 0.
- Hardness: 3/2 − ε is an inapproximability threshold for kCFL on stars when k = 1.The hardness result applies to the cable-unsplittable demand setting.
- Resource-augmented algorithm: Optimal cost is achieved for ε-resource-augmented kCFL on trees in time n^k·f(ε).The result is stated for 0 < ε ≤ 1/10 and extends from the single-cable case to a constant number of cable types.
- Approximation consequence: 2-approximation for the original cable-unsplittable kCFL follows by transforming the augmented solution into a feasible solution.Choosing ε = 1/10 yields the stated approximation guarantee.
4.1 RAkCFL on Trees for a Single Cable Type (k=1)
For one cable type, the algorithm rounds and groups demands, then uses dynamic programming to obtain an optimal-cost solution with bounded cable overload in polynomial time for fixed ε.
- Demand rounding and bundling: Demand rounding separates large and small demands, while small demands are grouped into bundles to control the dynamic program’s state space.The procedure rounds large demands and handles small demands through bundles and a leftover bundle; ε−1 is assumed to be an even integer.
- Guarantees: 5ε resource augmentation and optimal cost are achieved, because the recovered solution is feasible under the augmentation and no more expensive than an unaugmented optimum.Converting from rounded to original demands yields at most (1 + 5ε)µ demand on each cable.
- Guarantees: The algorithm runs in time nO(ε−2), giving an ε-resource augmented optimal-cost solution for the single-cable case after rescaling ε.The presentation uses 5ε-resource augmentation before rescaling the parameter in the theorem.
- Dynamic program: The dynamic program stores rounded large-demand counts, small-demand totals traveling toward or from the parent, and the minimum subtree-serving cost.States are tuples (a, λs, ¯λs, c), with domination retaining the lower-cost state for identical demand information.
- Structural transformation: Small demands can be regrouped without changing facilities, cables, or large-demand paths, while keeping rounded demand on each cable within (1 + 2ε)µ.The no-crossing property for equal-valued demands supports restricting demand directions on each edge.
4.2 RAkCFL on Trees for a Constant Number of Cables
For a constant number of cable types, the dynamic program extends demand rounding, state vectors, and cable-cost computation across all types while retaining optimal cost and bounded resource augmentation.
- Generalized rounding: Large demands are rounded using the closest multiples of cable-specific units δi = ε2µi, while small demands use δs = ε2µ1/n.This provides an approximation within δi for each cable type and leaves at most kε−2 rounded possibilities for large demands.
- Dynamic program: The dynamic-programming state expands the large-demand vector to account for all k cable types while retaining small-demand totals in both directions.Indicator vectors for the cable-specific rounded demands are concatenated into the state representation.
- Guarantees: 5ε resource augmentation and optimal cost hold for the constant-cable algorithm, matching the single-type guarantees.These guarantees are stated as Claims 4.11 and 4.12 for the kCFL instance.
- Guarantees: The generalized algorithm runs in time nO(ε−2k).The exponent reflects the dependence on both the accuracy parameter and the number of cable types.
5 Deferred Proofs
The deferred proofs establish cable-selection approximation, structural properties for dynamic programming, hardness for cable-unsplittable demands, and resource-augmented optimal-cost solutions on trees.
- Cable selection: An (1 + ε)-approximation algorithm finds a minimum-cost cable bag with capacity at least λ in time poly(k, 1/ε).The method uses dynamic programming over non-dominated capacity-cost trade-offs and rounds costs to obtain polynomial dependence on k and 1/ε.
- Cable selection: 2-approximation follows by comparing one sufficiently capacious cable with repeated copies of the best capacity-to-cost cable.The analysis uses the cases of a cable with capacity at least λ and cables with capacity below λ.
- Structural lemmas: Splittable or unit-demand solutions admit an optimal routing without crossings, while uncapacitated solutions also admit no demand leaving an open facility.The no-crossing property is stated for monotone cable costs; the facility-crossing property applies in the uncapacitated setting.
- Structural lemmas: Unsplittable demands can require bidirectional flow across one edge, so the no-crossing lemma fails in that setting.In Example 5.1, demands from v2 and v3 traverse (v2, v3) in opposite directions simultaneously.
- Dynamic programming: An O(D)-state dynamic program stores, for each tree vertex, minimum subtree cost for each demand constraint λ ∈ [−D, D].The deferred proof describes total(v) as pairs of demand constraints and costs, yielding at most O(D) states per vertex.