One of the most fundamental problems in network design problems and complexity theory is the Steiner tree problem in which one is given an edgecost graph, and is asked to find a minimumcost subtree in the graph that spans a given subset of vertices, called terminals. This problem was given as one of the 21 NP complete problems in Karp’s list. In this thesis, we aim to investigate some variants of the Steiner tree problem. In the budgeted rooted Steiner tree problem, we are given a graph G with n nodes, a predefined node r, a cost function is associated to each edge/node and a prize function is associated to each node, and a realvalued budget B. The aim is to find a tree in G rooted at r such that the total cost is at most B and the total prize is maximized. In the quota rooted Steiner tree problem, we are given a realvalued quota Q, instead of the budget, and we aim at minimizing the cost of a tree rooted at r whose overall prize is at least Q. In this thesis, we study some relevant generalizations of the above problems, namely we consider: (i) directed graphs with monotone submodular prize functions over subsets of nodes, (ii) directed graphs with additive prize functions, and (iii) undirected graphs with monotone submodular prize functions. For scenario (i), we propose a polynomial time O(1ε3√B)approximation algorithm for the budgeted problem that violates the budget constraint by a factor of at most 1 + ε, for any ε ∈ (0, 1], where the costs are positive integers values associated to the edges. For scenario (ii), we develop a technique resorting on a standard flow based linear programming relaxation to compute a tree with good tradeoff between prize and cost, which allows us to provide very simple polynomial time approximation algorithms for both the budgeted and the quota problems. For the budgeted nodeweighted problem, our algorithm achieves an O(1ε2 n2/3 ln n)approximation at the cost of a budget violation of a factor of at most 1 + ε, for any ε ∈ (0, 1]. For the quota nodeweighted problem, our algorithm guarantees an approximation factor of O(n 2/3 ln n) at the cost of a violation of the quota constraint by a factor of at most 2. Our algorithms work for nonnegative realvalued costs and are the first nontrivial polynomial time algorithms with approximation factors depending on n. The same technique can be used to find an approximation algorithm for the nodeweighted directed Steiner tree problem (DSteinerT). Recently, Li and Laekhanukit [SODA 2022] ruled out polylogarithmic approximation algorithms for DSteinerT based on a standard flowbased linear programming relaxation. By using the same linear relaxation, we provide a surprisingly simple polynomial time O((1 + ε) √n ln n)approximation algorithm for DSteinerT, for any ε > 0. For scenario (iii), we provide a polynomial time O(1ε3√n log n) approximation algorithm for the nodeweighted budgeted problem that violates the budget constraint by a factor of at most 1 + ε, for any ε ∈ (0, 1]. Also in this case we introduce a general technique that exploits a flowbased linear program to find trees with a good tradeoff between prize and cost, which allows us to provide a good approximation also for the quota nodeweighted problem. Finally, we provide some new/improved approximation bounds for several related problems, including the undirected version of scenario (ii), the maximum budgeted connected set cover problem, and the budgeted sensor cover problem.
Approximation Algorithms for Constrained Steiner Tree Problems / Delfarazpahlevanloo, Esmaeil.  (2023 Mar 10).
Approximation Algorithms for Constrained Steiner Tree Problems
DELFARAZPAHLEVANLOO, ESMAEIL
20230310
Abstract
One of the most fundamental problems in network design problems and complexity theory is the Steiner tree problem in which one is given an edgecost graph, and is asked to find a minimumcost subtree in the graph that spans a given subset of vertices, called terminals. This problem was given as one of the 21 NP complete problems in Karp’s list. In this thesis, we aim to investigate some variants of the Steiner tree problem. In the budgeted rooted Steiner tree problem, we are given a graph G with n nodes, a predefined node r, a cost function is associated to each edge/node and a prize function is associated to each node, and a realvalued budget B. The aim is to find a tree in G rooted at r such that the total cost is at most B and the total prize is maximized. In the quota rooted Steiner tree problem, we are given a realvalued quota Q, instead of the budget, and we aim at minimizing the cost of a tree rooted at r whose overall prize is at least Q. In this thesis, we study some relevant generalizations of the above problems, namely we consider: (i) directed graphs with monotone submodular prize functions over subsets of nodes, (ii) directed graphs with additive prize functions, and (iii) undirected graphs with monotone submodular prize functions. For scenario (i), we propose a polynomial time O(1ε3√B)approximation algorithm for the budgeted problem that violates the budget constraint by a factor of at most 1 + ε, for any ε ∈ (0, 1], where the costs are positive integers values associated to the edges. For scenario (ii), we develop a technique resorting on a standard flow based linear programming relaxation to compute a tree with good tradeoff between prize and cost, which allows us to provide very simple polynomial time approximation algorithms for both the budgeted and the quota problems. For the budgeted nodeweighted problem, our algorithm achieves an O(1ε2 n2/3 ln n)approximation at the cost of a budget violation of a factor of at most 1 + ε, for any ε ∈ (0, 1]. For the quota nodeweighted problem, our algorithm guarantees an approximation factor of O(n 2/3 ln n) at the cost of a violation of the quota constraint by a factor of at most 2. Our algorithms work for nonnegative realvalued costs and are the first nontrivial polynomial time algorithms with approximation factors depending on n. The same technique can be used to find an approximation algorithm for the nodeweighted directed Steiner tree problem (DSteinerT). Recently, Li and Laekhanukit [SODA 2022] ruled out polylogarithmic approximation algorithms for DSteinerT based on a standard flowbased linear programming relaxation. By using the same linear relaxation, we provide a surprisingly simple polynomial time O((1 + ε) √n ln n)approximation algorithm for DSteinerT, for any ε > 0. For scenario (iii), we provide a polynomial time O(1ε3√n log n) approximation algorithm for the nodeweighted budgeted problem that violates the budget constraint by a factor of at most 1 + ε, for any ε ∈ (0, 1]. Also in this case we introduce a general technique that exploits a flowbased linear program to find trees with a good tradeoff between prize and cost, which allows us to provide a good approximation also for the quota nodeweighted problem. Finally, we provide some new/improved approximation bounds for several related problems, including the undirected version of scenario (ii), the maximum budgeted connected set cover problem, and the budgeted sensor cover problem.File  Dimensione  Formato  

2023_PhDThesis_Delfarazpahlevanloo.pdf
accesso aperto
Tipologia:
Tesi di dottorato
Licenza:
Accesso gratuito
Dimensione
1.82 MB
Formato
Adobe PDF

1.82 MB  Adobe PDF  Visualizza/Apri 
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.