Search

We introduce a novel domination problem, which we call Dual Domination (DD). We assume that the nodes in a network are partitioned into two categories: Positive nodes (V +) and negative nodes (V −). We study the Maximum Bounded Dual Domination , where, given a bound k , the problem is to find a set D ⊆ V + , which maximizes the number of nodes dominated in V + , dominating at most k nodes in V −. We show that such problem is hard to approximate to a factor better than (1 − 1 / e). We give a polynomial time algorithm with approximation guaranteed (1 − e − 1 / Δ) , where Δ represents the maximum number of neighbors in V + of any node in V − , and an O (| V | k 2) time algorithm to solve the problem on trees. We also study two related problems named Maximum Dual Domination and minimum Negative Dual Domination. For both problems, we show hardness results and provide O (| V |) time algorithms on trees. [ABSTRACT FROM AUTHOR]

• The placement of data and the scheduling of request are studied in edge caching. • Network unreliability and limited storage and bandwidth resources are considered. • Two algorithms with different computation complexity and cache efficiency are developed. • The experiments are conducted to evaluate the performance of proposed caching strategies. Edge caching is a prevailing media delivery technology where data is hosted at the edge nodes with computing and storage capability in close proximity to users, in order to expand the backhaul network capacity and enhance users' quality of experience (QoE). The existing work in this area often neglects the fact that large-scale distributed cache networks are not particularly reliable and many edge nodes are prone to failure. In this paper we investigate and develop a novel, cooperative caching mechanism for content placement and request routing. We aim to minimize the content access delay and achieve the optimization in polynomial time, taking into account failures in an unreliable network environment with limited edge storage and bandwidth. We introduce two optimization algorithms: 1) a primal-dual algorithm that is based on the Lagrangian dual decomposition and subgradient method, and 2) a greedy-based approximation algorithm with a proven approximation ratio. Numerical results show that the proposed algorithms outperform other comparative approaches in synthetic and real network environments, and the approximation algorithm is particularly suitable for networking scenarios with sparse node connectivity and resources in short supply. [ABSTRACT FROM AUTHOR]

We introduce a new class of scheduling problems in which the optimization is performed by the worker (single “machine”) who performs the tasks. A typical worker’s objective is to minimize the amount of work he does (he is “lazy”), or more generally, to schedule as inefficiently (in some sense) as possible. The worker is subject to the constraint that he must be busy when there is work that he can do; we make this notion precise both in the preemptive and nonpreemptive settings. The resulting class of “perverse” scheduling problems, which we denote “Lazy Bureaucrat Problems,” gives rise to a rich set of new questions that explore the distinction between maximization and minimization in computing optimal schedules. [Copyright &y& Elsevier]

Line of Sight (LoS) networks were designed to model wireless communication in settings which may contain obstacles. For fixed positive integer d , and positive integer ω , a graph G = (V , E) is a (d -dimensional) LoS network with range parameter ω if it can be embedded in a finite cube of the d -dimensional integer grid so that each pair of vertices in V are adjacent if and only if their embedding coordinates differ only in one position and such difference is less than ω. In this paper we investigate a dynamic programming (DP) approach which can be used to obtain efficient algorithmic solutions for various combinatorial problems in LoS networks. In particular DP solves the Maximum Independent Set (MIS) problem in LoS networks optimally, for any ω , on narrow LoS networks (i.e. networks which can be embedded in a k × k ... × k × n region, for some fixed k independent of n). In the unrestricted case it has been shown that the (decision version of the) problem is NP-hard when 2 < ω = O (n 1 − δ) , for fixed 0 < δ < 1. We describe how DP can be used as a building block in the design of good approximation algorithms in this case. In particular we present a semi-online polynomial-time approximation scheme for the MIS problem in narrow d -dimensional LoS networks, as well as a polynomial-time 2-approximation algorithm and a fast polynomial time approximation scheme for the MIS problem in arbitrary d -dimensional LoS networks. Finally we comment on how the approach can be adapted to prove similar results for a number of important optimization problems in LoS networks. [ABSTRACT FROM AUTHOR]