Search

In the general max–min fair allocation problem, there are m players and n indivisible resources, each player has his/her own utilities for the resources, and the goal is to find an assignment that maximizes the minimum total utility of resources assigned to a player. The problem finds many natural applications such as bandwidth distribution in telecom networks, processor allocation in computational grids, and even public-sector decision making. We introduce an over-estimation strategy to design approximation algorithms for this problem. When all utilities are positive, we obtain an approximation ratio of c 1 - ϵ , where c is the maximum ratio of the largest utility to the smallest utility of any resource. When some utilities are zero, we obtain an approximation ratio of (1 + 3 c ^ + O (δ c ^ 2)) , where c ^ is the maximum ratio of the largest utility to the smallest positive utility of any resource. [ABSTRACT FROM AUTHOR]

This study considers the soft capacitated vertex cover problem in a dynamic setting. This problem generalizes the dynamic model of the vertex cover problem, which has been intensively studied in recent years. Given a dynamically changing vertex-weighted graph G = (V , E) , which allows edge insertions and edge deletions, the goal is to design a data structure that maintains an approximate minimum vertex cover while satisfying the capacity constraint of each vertex. That is, when picking a copy of a vertex v in the cover, the number of v's incident edges covered by the copy is up to a given capacity of v. We extend Bhattacharya et al.'s work [SODA'15 and ICALP'15] to obtain a deterministic primal-dual algorithm for maintaining a constant-factor approximate minimum capacitated vertex cover with O (log n / ϵ) amortized update time, where n is the number of vertices in the graph. The algorithm can be extended to (1) a more general model in which each edge is associated with a non-uniform and unsplittable demand, and (2) the more general capacitated set cover problem. [ABSTRACT FROM AUTHOR]

In this paper, we study online algorithms for the Canadian Traveller Problem defined by Papadimitriou and Yannakakis in 1991. This problem involves a traveller who knows the entire road network in advance, and wishes to travel as quickly as possible from a source vertex s to a destination vertex t, but discovers online that some roads are blocked (e.g., by snow) once reaching them. Achieving a bounded competitive ratio for the problem is PSPACE-complete. Furthermore, if at most k roads can be blocked, the optimal competitive ratio for a deterministic online algorithm is 2 k + 1 , while the only randomized result known so far is a lower bound of k + 1 . We show, for the first time, that a polynomial time randomized algorithm can outperform the best deterministic algorithms when there are at least two blockages, and surpass the lower bound of 2 k + 1 by an o(1) factor. Moreover, we prove that the randomized algorithm can achieve a competitive ratio of (1 + 2 2) k + 2 in pseudo-polynomial time. The proposed techniques can also be exploited to implicitly represent multiple near-shortest s-t paths. [ABSTRACT FROM AUTHOR]

Based on the power observation rules, the problem of monitoring a power utility network can be transformed into the graph-theoretic power domination problem, which is an extension of the well-known domination problem. A set $$S$$ is a power dominating set (PDS) of a graph $$G=(V,E)$$ if every vertex $$v$$ in $$V$$ can be observed under the following two observation rules: (1) $$v$$ is dominated by $$S$$ , i.e., $$v \in S$$ or $$v$$ has a neighbor in $$S$$ ; and (2) one of $$v$$ 's neighbors, say $$u$$ , and all of $$u$$ 's neighbors, except $$v$$ , can be observed. The power domination problem involves finding a PDS with the minimum cardinality in a graph. Similar to message passing protocols, a PDS can be considered as a dominating set with propagation that applies the second rule iteratively. This study investigates a generalized power domination problem, which limits the number of propagation iterations to a given positive integer; that is, the second rule is applied synchronously with a bounded time constraint. To solve the problem in block graphs, we propose a linear time algorithm that uses a labeling approach. In addition, based on the concept of time constraints, we provide the first nontrivial lower bound for the power domination problem. [ABSTRACT FROM AUTHOR]

This study investigates a generalization of the Canadian Traveller Problem (CTP), which finds real applications in dynamic navigation systems used to avoid traffic congestion. Given a road network $$G=(V,E)$$ in which there is a source $$s$$ and a destination $$t$$ in $$V$$ , every edge $$e$$ in $$E$$ is associated with two possible distances: original $$d(e)$$ and jam $$d^+(e)$$ . A traveller only finds out which one of the two distances of an edge upon reaching an end vertex incident to the edge. The objective is to derive an adaptive strategy for travelling from $$s$$ to $$t$$ so that the competitive ratio, which compares the distance traversed with that of the static $$s,t$$ -shortest path in hindsight, is minimized. This problem was initiated by Papadimitriou and Yannakakis. They proved that it is PSPACE-complete to obtain an algorithm with a bounded competitive ratio. In this paper, we propose tight lower bounds of the problem when the number of 'traffic jams' is a given constant $$k$$ ; and we introduce a deterministic algorithm with a $$\mathrm{min}\{ r, 2k+1\}$$ -ratio, which meets the proposed lower bound, where $$r$$ is the worst-case performance ratio. We also consider the Recoverable CTP, where each blocked edge is associated with a recovery time to reopen. Finally, we discuss the uniform jam cost model, i.e., for every edge $$e$$ , $$d^+(e) = d(e) + c$$ , for a constant $$c$$ . [ABSTRACT FROM AUTHOR]

A set S⊆ V is a power dominating set (PDS) of a graph G=( V, E) if every vertex and every edge in G can be observed based on the observation rules of power system monitoring. The power domination problem involves minimizing the cardinality of a PDS of a graph. We consider this combinatorial optimization problem and present a linear time algorithm for finding the minimum PDS of an interval graph if the interval ordering of the graph is provided. In addition, we show that the algorithm, which runs in Θ( nlog n) time, where n is the number of intervals, is asymptotically optimal if the interval ordering is not given. We also show that the results hold for the class of circular-arc graphs. [ABSTRACT FROM AUTHOR]

We consider a generalization of the well-known domination problem on graphs. The ( soft) capacitated domination problem with demand constraints is to find a dominating set D of minimum cardinality satisfying both the capacity and demand constraints. The capacity constraint specifies that each vertex has a capacity that it can use to meet the demands of dominated vertices in its closed neighborhood, and the number of copies of each vertex allowed in D is unbounded. The demand constraint specifies the demand of each vertex in V to be met by the capacities of vertices in D dominating it. In this paper, we study the capacitated domination problem on trees from an algorithmic point of view. We present a linear time algorithm for the unsplittable demand model, and a pseudo-polynomial time algorithm for the splittable demand model. In addition, we show that the capacitated domination problem on trees with splittable demand constraints is NP-complete (even for its integer version) and provide a polynomial time approximation scheme (PTAS). We also give a primal-dual approximation algorithm for the weighted capacitated domination problem with splittable demand constraints on general graphs. [ABSTRACT FROM AUTHOR]