To find a maximum number of communication requests that can be satisfied concurrently, is a fundamental network scheduling problem. In this work we investigate the problem of finding a maximum number of multicast requests that can be scheduled simultaneously in a tree network in which the edges and links have heterogeneous bandwidth limitations.This problem generalizes two problems studied in the literature: maximum k-colorable subgraph in chordal graphs, maximum multi-commodity flow in trees. The problem is NP-hard and admits a 1.585-approximation in the special case of homogeneous bandwidth limitations.We first show that the problem is harder to approximate when the bandwidth limitations are heterogeneous, i.e. vary from link to link and from node to node. We then generalize of a classical algorithm and obtain an M-approximation where M is the maximum number of leaves of the communication subtrees. Surprisingly, variants of the same algorithm, are used in the literature at least four times to solve related problems. There exists a polynomial-time algorithm for the special case of unicast requests and star topology. We generalize this result and relax the second requirement so that the set of unicast requests share a common vertex with no restriction on the tree topology.

We consider the online version of the coalition structure generation problem, in which agents, corresponding to the vertices of a graph, appear in an online fashion and have to be partitioned into coalitions by an authority (i.e., an online algorithm). When an agent appears, the algorithm has to decide whether to put the agent into an existing coalition or to create a new one containing, at this moment, only her. The decision is irrevocable. The objective is partitioning agents into coalitions so as to maximize the resulting social welfare that is the sum of all coalition values. We consider two cases for the value of a coalition: (1) the sum of the weights of its edges, and (2) the sum of the weights of its edges divided by its size. Coalition structures appear in a variety of application in AI, multi-agent systems, networks, as well as in social networks, data analysis, computational biology, game theory, and scheduling. For each of the coalition value functions we consider the bounded and unbounded cases depending on whether or not the size of a coalition can exceed a given value α. Furthermore, we consider the case of a limited number of coalitions and various weight functions for the edges, i.e., unrestricted, positive and constant weights. We show tight or nearly tight bounds for the competitive ratio in each case.

Abstract We study the minimum diameter spanning tree problem under the reload cost model (Diameter‐Treefor short) introduced by Wirth and Steffan. In this problem, given an undirected edge‐colored graphG, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree ofGof minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of theDiameter‐Treeproblem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree Δ of the input graph. We prove thatDiameter‐Treeispara‐NP‐hard for any combination of two of these three parameters, and that it isFPTparameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we proveDiameter‐Treeto beNP‐hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan proved that the problem can be solved in polynomial time on graphs with Δ = 3, and Galbiati proved that it isNP‐hard if Δ = 4. Our results show, in particular, that without the requirement of the triangle inequality, the problem isNP‐hard if Δ = 3, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove thatDiameter‐Treeis inXPandW[1]‐hard parameterized by the treewidth plus Δ.

Abstract In an edge‐colored graph, a traversal cost occurs along a path when consecutive edges with different colors are traversed. The value of the traversal cost depends only on the colors of the edges. Two related global cost measures, namely the reload cost and the changeover cost with applications in telecommunications, transportation networks, and energy distribution networks have been studied in the literature. Previous work focused on problems with an edge‐colored graph being part of the input. In this paper, we formulate problems that aim to find an edge coloring of a graph minimizing the reload and changeover costs. One pair of problems aims to find a proper edge coloring to minimize the reload/changeover cost of a set of paths. Another pair of problems aim to find a proper edge coloring and a spanning tree to minimize the reload/changeover cost. We present several hardness results and polynomial‐time solvable special cases.

We study the minimum diameter spanning tree problem under the reload cost model (DIAMETER-TREE for short) introduced by Wirth and Steffan (2001). In this problem, given an undirected edge-colored graph G, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree of G of minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of the DIAMETER-TREE problem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree Delta of the input graph. We prove that DIAMETER-TREE is para-np-hard for any combination of two of these three parameters, and that it is FPT parameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we prove DIAMETER-TREE to be NP-hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan (2001) proved that the problem can be solved in polynomial time on graphs with Delta=3, and Galbiati (2008) proved that it is NP-hard if Delta=4. Our results show, in particular, that without the requirement of the triangle inequality, the problem is NP-hard if Delta=3, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove that DIAMETER-TREE is in XP and W[1]-hard parameterized by the treewidth plus Delta.

We focus on throughput-maximizing, max-min fair, and proportionally fair scheduling problems for centralized cognitive radio networks. First, we propose a polynomial-time algorithm for the throughput-maximizing scheduling problem. We then elaborate on certain special cases of this problem and explore their combinatorial properties. Second, we prove that the max-min fair scheduling problem is NP-Hard in the strong sense. We also prove that the problem cannot be approximated within any constant factor better than 2 unless P=NP. Additionally, we propose an approximation algorithm for the max-min fair scheduling problem with approximation ratio depending on the ratio of the maximum possible data rate to the minimum possible data rate of a secondary users. We then focus on the combinatorial properties of certain special cases and investigate their relation with various problems such as the multiple-knapsack, matching, terminal assignment, and Santa Claus problems. We then prove that the proportionally fair scheduling problem is NP-Hard in the strong sense and inapproximable within any additive constant less than log(4/3). Finally, we evaluate the performance of our approximation algorithm for the max-min fair scheduling problem via simulations. This approach sheds light on the complexity and combinatorial properties of these scheduling problems, which have high practical importance in centralized cognitive radio networks.

We consider the following fundamental scheduling problem in which the input consists of n jobs to be scheduled on a set of identical machines of bounded capacity g (which is the maximal number of jobs that can be processed simultaneously by a single machine). Each job is associated with a start time and a completion time, it is supposed to be processed from the start time to the completion time (and in one of our extensions it has to be scheduled also in a continuous number of days, this corresponds to a two-dimensional version of the problem). We consider two versions of the problem. In the scheduling minimization version the goal is to minimize the total busy time of machines used to schedule all jobs. In the resource allocation maximization version the goal is to maximize the number of jobs that are scheduled for processing under a budget constraint given in terms of busy time. This is the first study of the maximization version of the problem. The minimization problem is known to be NP-Hard, thus the maximization problem is also NP-Hard. We consider various special cases, identify cases where an optimal solution can be computed in polynomial time, and mainly provide constant factor approximation algorithms for both minimization and maximization problems. Some of our results improve upon the best known results for this job scheduling problem. Our study has applications in power consumption, cloud computing and optimizing switching cost of optical networks.

The placement of regenerators in optical networks has become an active area of research during the last few years. Given a set of lightpaths in a network$G$and a positive integer$d$, regenerators must be placed in such a way that in any lightpath there are no more than$d$hops without meeting a regenerator. The cost function we consider is given by the total number of regenerators placed at the nodes, which we believe to be a more accurate estimation of the real cost of the network than the number of locations considered in the work of Flammini(IEEE/ACM Trans. Netw., vol. 19, no. 2, pp. 498–511, Apr. 2011). Furthermore, in our model we assume that we are given a finite set of$p$possible traffic patterns (each given by a set of lightpaths), and our objective is to place the minimum number of regenerators at the nodes so that each of the traffic patterns is satisfied. While this problem can be easily solved when$d=1$or$p=1$, we prove that for any fixed$d,p \geq 2$, it does not admit a PTAS, even if$G$has maximum degree at most 3 and the lightpaths have length$ {\cal O}(d)$. We complement this hardness result with a constant-factor approximation algorithm with ratio$\ln (d \cdot p)$. We then study the case where$G$is a path, proving that the problem is polynomial-time solvable for two particular families of instances. Finally, we generalize our model in two natural directions, which allows us to capture the model of Flamminias a particular case, and we settle some questions that were left open therein.

We consider a scheduling problem in which a bounded number of jobs can be processed simultaneously by a single machine. The input is a set of n jobs J = {J1,..., Jn}. Each job, Jj, is associated with an interval [sj, cj] along which it should be processed. Also given is the parallelism parameter g ges 1, which is the maximal number of jobs that can be processed simultaneously by a single machine. Each machine operates along a contiguous time interval, called its busy interval, which contains all the intervals corresponding to the jobs it processes. The goal is to assign the jobs to machines such that the total busy time of the machines is minimized. The problem is known to be NP-hard already for g = 2. We present a 4-approximation algorithm for general instances, and approximation algorithms with improved ratios for instances with bounded lengths, for instances where any two intervals intersect, and for instances where no interval is properly contained in another. Our study has important application in optimizing the switching costs of optical networks.

SONET ADMs are dominant cost factors in WDM/SONET rings. Whereas most previous papers on the topic concentrated on the number of wavelengths assigned to a given set of lightpaths, more recent papers argue that the number of ADMs is a more realistic cost measure. Some of these works discuss various heuristic algorithms for this problem, and the best known result is a 3/2 approximation in G. Calinescu and P.J. Wan (2001). Through the study of the relation between this problem and the problem of finding maximum disjoint rings in a given set of lightpaths we manage to shed more light onto this problem and to develop a 10/7 + /spl epsi/ approximation for it.