Search

The edge dominating set problem (EDS) is to compute a minimum size edge set such that every edge is dominated by some edge in it. This paper considers a variant of EDS with extensions of multiple and connected dominations combined. In the b-EDS problem, each edge needs to be dominated b times. Connected EDS requires an edge dominating set to be connected while it has to form a tree in Tree Cover. Although each of EDS, b-EDS, and Connected EDS (or Tree Cover) has been well studied, each known to be approximable within 2 (or 8/3 for b-EDS in general), nothing is known when these extensions are imposed simultaneously on EDS unlike in the case of the (vertex) dominating set problem. We consider Connected 2-EDS and 2-Tree Cover (i.e., a combination of 2-EDS and Tree Cover), and present a polynomial algorithm approximating each within 2. Moreover, it will be shown that the single tree computed is no larger than twice the optimum for (not necessarily connected) 2-EDS, thus also approximating 2-EDS equally well. It also implies that 2-EDS with clustering properties can be approximated within 2 as well. [ABSTRACT FROM AUTHOR]

We present a greedy algorithm for the directed Steiner tree problem (DST), where any tree rooted at any (uncovered) terminal can be a candidate for greedy choice. It will be shown that the algorithm, running in polynomial time for any constant $$l$$ , outputs a directed Steiner tree of cost no larger than $$2(l-1)(\ln n+1)$$ times the cost of any $$l$$ -restricted Steiner tree, which is such a Steiner tree in which every terminal is at most $$l$$ arcs away from the root or another terminal. We derive from this result that (1) DST for a class of graphs, including quasi-bipartite graphs, in which the length of paths induced by Steiner vertices is bounded by some constant can be approximated within a factor of $$O(\log n)$$ , and (2) the tree cover problem on directed graphs can also be approximated within a factor of $$O(\log n)$$ . [ABSTRACT FROM AUTHOR]

The multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has several lease options besides the pure rent and buy options. In this problem the hardness of an instance, which is the setting of options, significantly affects the player's performance. There is an algorithm that for a given instance, computes the best possible strategy. However, the output is given as numerical values and therefore the relational nature between an instance and the best possible performance for it has not been known. In this paper we prove that even for the easiest instance, a competitive ratio smaller than $$e/(e - 1) \approx 1.58$$ cannot be achieved. More precisely, a tight lower bound on the best possible performance is obtained in a closed form parametrized by the number of options. Furthermore, we establish a matching upper and lower bound on the competitive ratio each for the 3-option and 4-option problems. [ABSTRACT FROM AUTHOR]

We study the approximability of the weighted edge-dominating set problem. Although even the unweighted case is NP-Complete, in this case a solution of size at most twice the minimum can be efficiently computed due to its close relationship with minimum maximal matching; however, in the weighted case such a nice relationship is not known to exist. In this paper, after showing that weighted edge domination is as hard to approximate as the well studied weighted vertex cover problem, we consider a natural strategy, reducing edge-dominating set to edge cover. Our main result is a simple $$2\frac{1}{{10}}$$ -approximation algorithm for the weighted edge-dominating set problem, improving the existing ratio, due to a simple reduction to weighted vertex cover, of 2 rWVC, where rWVC is the approximation guarantee of any polynomial-time weighted vertex cover algorithm. The best value of rWVC currently stands at $$2 - \frac{{\log \log \left| V \right|}}{{2\log \left| V \right|}}$$ . Furthermore we establish that the factor of $$2\frac{1}{{10}}$$ is tight in the sense that it coincides with the integrality gap incurred by a natural linear programming relaxation of the problem. [ABSTRACT FROM AUTHOR]