ﻻ يوجد ملخص باللغة العربية
The Steiner Tree problem is a classical problem in combinatorial optimization: the goal is to connect a set $T$ of terminals in a graph $G$ by a tree of minimum size. Karpinski and Zelikovsky (1996) studied the $delta$-dense version of {sc Steiner Tree}, where each terminal has at least $delta |V(G)setminus T|$ neighbours outside $T$, for a fixed $delta > 0$. They gave a PTAS for this problem. We study a generalization of pairwise $delta$-dense {sc Steiner Forest}, which asks for a minimum-size forest in $G$ in which the nodes in each terminal set $T_1,dots,T_k$ are connected, and every terminal in $T_i$ has at least $delta |T_j|$ neighbours in $T_j$, and at least $delta|S|$ nodes in $S = V(G)setminus (T_1cupdotscup T_k)$, for each $i, j$ in ${1,dots, k}$ with $i eq j$. Our first result is a polynomial-time approximation scheme for all $delta > 1/2$. Then, we show a $(frac{13}{12}+varepsilon)$-approximation algorithm for $delta = 1/2$ and any $varepsilon > 0$. We also consider the $delta$-dense Group Steiner Tree problem as defined by Hauptmann and show that the problem is $mathsf{APX}$-hard.
In the Priority Steiner Tree (PST) problem, we are given an undirected graph $G=(V,E)$ with a source $s in V$ and terminals $T subseteq V setminus {s}$, where each terminal $v in T$ requires a nonnegative priority $P(v)$. The goal is to compute a min
We study the prize-collecting version of the Node-weighted Steiner Tree problem (NWPCST) restricted to planar graphs. We give a new primal-dual Lagrangian-multiplier-preserving (LMP) 3-approximation algorithm for planar NWPCST. We then show a ($2.88
The restless bandit problem is one of the most well-studied generalizations of the celebrated stochastic multi-armed bandit problem in decision theory. In its ultimate generality, the restless bandit problem is known to be PSPACE-Hard to approximate
We give new approximation algorithms for the submodular joint replenishment problem and the inventory routing problem, using an iterative rounding approach. In both problems, we are given a set of $N$ items and a discrete time horizon of $T$ days in
Given a graph $G = (V,E)$ and a subset $T subseteq V$ of terminals, a emph{Steiner tree} of $G$ is a tree that spans $T$. In the vertex-weighted Steiner tree (VST) problem, each vertex is assigned a non-negative weight, and the goal is to compute a m