The Weighted Tree Augmentation Problem (WTAP) is a fundamental well-studied problem in the field of network design. Given an undirected tree G =( V , E ), an additional set of edges L ⊑ V × V disjoint from E called links and a cost vector c ∈ R ≥ 0 L , WTAP asks to find a minimum-cost set F ⊑ L with the property that ( V , E ∪ F ) is 2-edge connected. The special case where c ℓ = 1 for all ℓ ∈ L is called the Tree Augmentation Problem (TAP). For the class of bounded cost vectors, we present the first improved approximation algorithm for WTAP in more than three decades. Concretely, for any M ∈ R ≥ 1 and ε > 0, we present an LP based (μ +ϵ)-approximation for WTAP restricted to cost vectors c in [1, M ] L for μ ≈ 1.96417. More generally, our result is a (μ +ϵ)-approximation algorithm with running time n r O (1) , where r = c max / c min is the ratio between the largest and the smallest cost of any link. For the special case of TAP, we improve this factor to 5/3+ϵ. Our results rely on several new ideas, including a new LP relaxation of WTAP and a two-phase rounding algorithm. In the first phase, the algorithm uses the fractional LP solution to guide a simple decomposition method that breaks the tree into well-structured trees and equips each with a part of the fraction LP solution. In the second phase, the fractional solution in each part of the decomposition is rounded to an integral solution with two rounding procedures and the best outcome is included in the solution. One rounding procedure exploits the constraints in the new LP, while the other one exploits a connection to the Edge Cover Problem. We show that both procedures cannot have a bad approximation guarantee simultaneously to obtain the claimed approximation factor.

The Firefighter problem and a variant of it, known as Resource Minimization for Fire Containment (RMFC), are natural models for optimal inhibition of harmful spreading processes. Despite considerable progress on several fronts, the approximability of these problems is still badly understood. This is the case even when the underlying graph is a tree, which is one of the most-studied graph structures in this context and the focus of this article. In their simplest version, a fire spreads from one fixed vertex step by step from burning to adjacent non-burning vertices, and at each time step B many non-burning vertices can be protected from catching fire. The Firefighter problem asks, for a given B , to maximize the number of vertices that will not catch fire, whereas RMFC (on a tree) asks to find the smallest B that allows for saving all leaves of the tree. Prior to this work, the best known approximation ratios were an O (1)-approximation for the Firefighter problem and an O (log * n )-approximation for RMFC, both being LP-based and essentially matching the integrality gaps of two natural LP relaxations. We improve on both approximations by presenting a PTAS for the Firefighter problem and an O (1)-approximation for RMFC, both qualitatively matching the known hardness results. Our results are obtained through a combination of the known LPs with several new techniques, which allow for efficiently enumerating over super-constant size sets of constraints to strengthen the natural LPs.

The Weighted Tree Augmentation Problem (WTAP) is a fundamental well-studied problem in the field of network design. Given an undirected tree G = (V,E), an additional set of edges L ⊆ V × V disjoint from E called links and a cost vector WTAP asks to find a minimum-cost set F c L with the property that (V, E ∪ F) is 2-edge connected. The special case where cℓ = 1 for all ℓ ℓ L is called the Tree Augmentation Problem (TAP). For the class of bounded cost vectors, we present a first improved approximation algorithm for WTAP since more than three decades. Concretely, for any M G r≥1 and ∊ > 0, we present an LP based (δ + ∊)-approximation for WTAP restricted to cost vectors c in [1,M]L for δ ≈ 1.96417. More generally, our result is a (δ + ∊)-approximation algorithm with running time where r = cmax/cmin is the ratio between the largest and the smallest cost of any link. For the special case of TAP we improve this factor to | + e. Our results rely on several new ideas, including a new LP relaxation of WTAP and a two-phase rounding algorithm. In the first phase, the algorithm uses the fractional LP solution to guide a simple decomposition method that breaks the tree into well-structured trees and equips each tree with a part of the fraction LP solution. In the second phase, the fractional solution in each part of the decomposition is rounded to an integral solution with two rounding procedures, and the best outcome is included in the solution. One rounding procedure exploits the constraints in the new LP, while the other one exploits a connection to the Edge Cover Problem. We show that both procedures can not have a bad approximation guarantee simultaneously to obtain the claimed approximation factor.

The Firefighter problem and a variant of it, known as Resource Minimization for Fire Containment (RMFC), are natural models for optimal inhibition of harmful spreading processes. Despite considerable progress on several fronts, the approximability of these problems is still badly understood. This is the case even when the underlying graph is a tree, which is one of the most- studied graph structures in this context and the focus of this paper. In their simplest version, a fire spreads from one fixed vertex step by step from burning to adjacent non-burning vertices, and at each time step B many non-burning vertices can be protected from catching fire. The Firefighter problem asks, for a given B, to maximize the number of vertices that will not catch fire, whereas RMFC (on a tree) asks to find the smallest B that allows for saving all leaves of the tree. Prior to this work, the best known approximation ratios were an O(1)-approximation for the Firefighter problem and an O(log* n)-approximation for RMFC, both being LP-based and essentially matching the integrality gaps of two natural LP relaxations. We improve on both approximations by presenting a PTAS for the Firefighter problem and an O(1)-approximation for RMFC, both qualitatively matching the known hardness results. Our results are obtained through a combination of the known LPs with several new techniques, which allow for efficiently enumerating over super-constant size sets of constraints to strengthen the natural LPs.

Many real-life planning problems require making a priori decisions before all parameters of the problem have been revealed. An important special case of such problem arises in scheduling and transshipment problems, where a set of jobs needs to be assigned to the available set of machines or personnel (resources), in a way that all jobs have assigned resources, and no two jobs share the same resource. In its nominal form, the resulting computational problem becomes the assignment problem. This paper deals with the Robust Assignment Problem (RAP) which models situations in which certain assignments are vulnerable and may become unavailable after the solution has been chosen. The goal is to choose a minimum-cost collection of assignments (edges in the corresponding bipartite graph) so that if any vulnerable edge becomes unavailable, the remaining part of the solution contains an assignment of all jobs. We develop algorithms and hardness results for RAP and establish several connections to well-known concepts from matching theory, robust optimization, LP-based techniques and combinations thereof.

We prove a representation theorem of projections of sets of integer points by an integer matrix $W$. Our result can be seen as a polyhedral analogue of several classical and recent results related to the Frobenius problem. Our result is motivated by a large class of nonlinear integer optimization problems in variable dimension. Concretely, we aim to optimize $f(Wx)$ over a set $\mathcal{F} = P\cap \mathbb{Z}^n$, where $f$ is a nonlinear function, $P\subset \mathbb{R}^n$ is a polyhedron, and $W\in \mathbb{Z}^{d\times n}$. As a consequence of our representation theorem, we obtain a general efficient transformation from the latter class of problems to integer linear programming. Our bounds depend polynomially on various important parameters of the input data leading, among others, to first polynomial time algorithms for several classes of nonlinear optimization problems.

We consider a combinatorial optimization problem in passive In-Building Distributed Antenna Systems (IB-DAS) deployment for indoor mobile broadband service. These systems have a tree topology, in which a central base station is connected to a number of antennas located at tree leaves via cables represented by the tree edges. Each inner node corresponds to a power equipment, of which the available types differ in the number of output ports and/or by power gain at the ports. This paper focuses on the equipment selection problem that amounts to, for a given passive DAS tree topology, selecting a power equipment type for each inner node and assigning the outgoing edges of the node to the equipment ports. The performance metric is the power deviation at the antennas from the target values. We consider as objective function the minimization of either the total or the largest power deviation over all antennas. Our contributions are the development of exact pseudo-polynomial time algorithms and (additive) fully-polynomial time approximation schemes for both objectives. Numerical results are provided to illustrate the algorithms. We also extend some results to account for equipment cost.