Guha et al. [STOC, 1999] and Moss and Rabani [SIAM J. Comput., 2007] introduced two variants of the Steiner problem in undirected graphs in which the nodes are associated with two values, called costs and prizes. In the budgeted rooted node-weighted Steiner tree problem, we are given an undirected graph G with n nodes, a predefined node r, costs and prizes associated to the nodes of G, and a budget . The aim is to find a tree in G rooted at r such that the total cost of its nodes is at most and the total prize is maximized. In the quota rooted node-weighted Steiner tree problem, we are given a quota , instead of the budget, and we aim at minimizing the cost of a tree rooted at r whose overall prize is at least . If the graph is undirected both problems can be approximated within polylogarithmic factors, possibly with a constant-factor budget violation, [Bateni et al. SIAM J. Comput., 2018][Moss and Rabani SIAM J. Comput., 2007]. If the graph is directed, the budgeted problem can be approximated within a factor in quasi-polynomial time, where is the number of vertices in an optimal solution [Ghuge and Nagarajan SODA 2020], and within a factor with a budget violation of , for any , in polynomial time [D’Angelo, Delfaraz, and Gilbert ISAAC 2022]. In this paper, we provide two algorithms for the budgeted and quota problems on directed graphs that achieve, respectively, an -approximation at the cost of a budget violation of a factor of at most , for any , and an approximation factor of at the cost of a violation of the quota constraint by a factor of at most 2. We develop a technique resorting on a standard flow-based linear programming relaxation to compute a tree with good trade-off between prize and cost, which allows us to provide polynomial time approximation algorithms for both problems. We provide the first approximation algorithms for these problems that run in polynomial time and guarantee an approximation factor depending only on the number of vertices n.
Approximation Algorithms for Node-Weighted Directed Steiner Problems
D'Angelo, Gianlorenzo;Delfarazpahlevanloo, Esmaeil
2024-01-01
Abstract
Guha et al. [STOC, 1999] and Moss and Rabani [SIAM J. Comput., 2007] introduced two variants of the Steiner problem in undirected graphs in which the nodes are associated with two values, called costs and prizes. In the budgeted rooted node-weighted Steiner tree problem, we are given an undirected graph G with n nodes, a predefined node r, costs and prizes associated to the nodes of G, and a budget . The aim is to find a tree in G rooted at r such that the total cost of its nodes is at most and the total prize is maximized. In the quota rooted node-weighted Steiner tree problem, we are given a quota , instead of the budget, and we aim at minimizing the cost of a tree rooted at r whose overall prize is at least . If the graph is undirected both problems can be approximated within polylogarithmic factors, possibly with a constant-factor budget violation, [Bateni et al. SIAM J. Comput., 2018][Moss and Rabani SIAM J. Comput., 2007]. If the graph is directed, the budgeted problem can be approximated within a factor in quasi-polynomial time, where is the number of vertices in an optimal solution [Ghuge and Nagarajan SODA 2020], and within a factor with a budget violation of , for any , in polynomial time [D’Angelo, Delfaraz, and Gilbert ISAAC 2022]. In this paper, we provide two algorithms for the budgeted and quota problems on directed graphs that achieve, respectively, an -approximation at the cost of a budget violation of a factor of at most , for any , and an approximation factor of at the cost of a violation of the quota constraint by a factor of at most 2. We develop a technique resorting on a standard flow-based linear programming relaxation to compute a tree with good trade-off between prize and cost, which allows us to provide polynomial time approximation algorithms for both problems. We provide the first approximation algorithms for these problems that run in polynomial time and guarantee an approximation factor depending only on the number of vertices n.File | Dimensione | Formato | |
---|---|---|---|
PostPrint_2024_IWOCA 2024_14764_Dangelo.pdf
accesso aperto
Tipologia:
Documento in Post-print
Licenza:
Creative commons
Dimensione
373.7 kB
Formato
Adobe PDF
|
373.7 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.