This paper considers a parallel-machine scheduling problem with machine maintenance. There are unavailable periods on each of the first k machines, and the remaining m k machines are always available, where 1 <= k ...
详细信息
This paper considers a parallel-machine scheduling problem with machine maintenance. There are unavailable periods on each of the first k machines, and the remaining m k machines are always available, where 1 <= k <= m is an integer. The objective is to minimize the total completion time of all jobs. We show the classical SPT algorithm has a worst-case ratio of at most 1 + m-1/m-k when k < m. If there is exactly one unavailable period on each of the first k machines, and the unavailable periods do not overlap, the worst-case ratio of SPT is at most 2 + k-1/m-1, and no polynomial time approximation algorithm with worst-case ratio less than m/m-1 can exist when k = m unless P= NP. (C) 2011 Elsevier B.V. All rights reserved.
The p-radius characterizes the average rate of growth of norms of matrices in a multiplicative semigroup. This quantity has found several applications in recent years. We raise the question of its computability. We pr...
详细信息
The p-radius characterizes the average rate of growth of norms of matrices in a multiplicative semigroup. This quantity has found several applications in recent years. We raise the question of its computability. We prove that the complexity of its approximation increases exponentially with p. We then describe a series of approximations that converge to the p-radius with a priori computable accuracy. For nonnegative matrices, this gives efficient approximation schemes for the p-radius computation.
We consider the problem of finding a strictly fundamental cycle basis of minimum weight in the cycle space associated with an undirected connected graph G, where a nonnegative weight is assigned to each edge of G and ...
详细信息
We consider the problem of finding a strictly fundamental cycle basis of minimum weight in the cycle space associated with an undirected connected graph G, where a nonnegative weight is assigned to each edge of G and the total weight of a basis is defined as the sum of the weights of all the cycles in the basis. Several heuristics have been proposed to tackle this NP-hard problem, which has some interesting applications. In this paper we show that this problem is APX-hard, even when restricted to unweighted graphs, and hence does not admit a polynomial-time approximation scheme, unless P = NP. Using a recent result on the approximability of lower-stretch spanning trees (Elkin et al. (2005) [7]), we obtain that the problem is approximable within O(log(2) n log log n) for arbitrary graphs. We obtain tighter approximability bounds for dense graphs. In particular, the problem restricted to complete graphs admits a polynomial-time approximation scheme. (C) 2010 Elsevier B.V. All rights reserved.
Cost efficiency is a key aspect in deploying distributed service in networks within decentralized service delivery architectures. In this paper, we address this aspect from an optimization and algorithmic standpoint. ...
详细信息
Cost efficiency is a key aspect in deploying distributed service in networks within decentralized service delivery architectures. In this paper, we address this aspect from an optimization and algorithmic standpoint. The research deals with the placement of service components to network sites, where the performance metric is the cost for acquiring components between the sites. The resulting optimization problem, which we refer to as the k-Component Multi-site Placement Problem, is applicable to service distribution in a wide range of communication networking scenarios. We provide a theoretical analysis of the problem's computational complexity, and develop an integer programming model for providing reference results for performance benchmarking. On the algorithmic side, we present four approaches: an algorithm with approximation guarantee and three heuristics algorithms. The first heuristic is derived from graph theory on domatic partition. The second heuristic, built on intuition, admits distributed computation. The third heuristic emphasizes on fairness in cost distribution among the sites. We report simulation results for sets of networks where cost is represented by round-trip time (RTT) originating from real measurements. For small networks, the integer model is used to study algorithm performance in terms of optimality. Large networks are used to compare the algorithms relatively to each other. Among the algorithms, the heuristic based on intuition has close-to-optimal performance, and the fairness heuristic achieves a good balance between single-site cost and the overall one. In addition, the experiments demonstrate the significance of optimization for cost reduction in comparison to a the random allocation strategy. (C) 2011 Elsevier B.V. All rights reserved.
We obtain hardness results and approximation algorithms for two related geometric problems involving movement. The first is a constrained variant of the k-center problem, arising from a geometric client-server problem...
详细信息
We obtain hardness results and approximation algorithms for two related geometric problems involving movement. The first is a constrained variant of the k-center problem, arising from a geometric client-server problem. The second is the problem of moving points towards an independent set. (C) 2011 Elsevier B.V. All rights reserved.
We investigate the construction of prefix-free and fix-free codes with specified codeword compositions. We present a polynomial time algorithm which constructs a fix-free code with the same codeword compositions as a ...
详细信息
We investigate the construction of prefix-free and fix-free codes with specified codeword compositions. We present a polynomial time algorithm which constructs a fix-free code with the same codeword compositions as a given code for a special class of codes called distinct codes. We consider the construction of optimal fix-free codes which minimize the average codeword cost for general letter costs with uniform distribution of the codewords and present an approximation algorithm to find a near optimal fix-free code with a given constant cost. (C) 2011 Elsevier B.V. All rights reserved.
We address the problem of data gathering in a wireless network using multi-hop communication;our main goal is the analysis of simple algorithms suitable for implementation in realistic scenarios. We study the performa...
详细信息
We address the problem of data gathering in a wireless network using multi-hop communication;our main goal is the analysis of simple algorithms suitable for implementation in realistic scenarios. We study the performance of distributed algorithms, which do not use any form of local coordination, and we focus on the objective of minimizing average flow times of data packets. We prove a lower bound of Omega(n) on the expected competitive ratio of any acknowledgment-based distributed algorithm minimizing the maximum flow time, where n is the number of nodes of the network. Next, we consider a distributed algorithm which sends packets over shortest paths, and we use resource augmentation to analyze its performance when the objective is to minimize the average flow time. If interferences are modeled as in Bar-Yehuda et al. [R. Bar-Yehuda, O. Goldreich, A. Itai, On the time complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization. Journal of Computer and Systems Sciences 45 (1) (1992) 104-126] we prove that the algorithm is (1 + epsilon)-competitive, when the algorithm sends packets a factor O(log(delta/epsilon) log Delta) faster than the optimal off-line solution;here delta is the radius of the network and Delta, the maximum degree. We finally extend this result to a more complex interference model. (C) 2010 Elsevier B.V. All rights reserved.
This paper is motivated by operating self service transport systems that flourish nowadays. In cities where such systems have been set up with bikes, trucks travel to maintain a suitable number of bikes per station. I...
详细信息
This paper is motivated by operating self service transport systems that flourish nowadays. In cities where such systems have been set up with bikes, trucks travel to maintain a suitable number of bikes per station. It is natural to study a version of the C-delivery TSP defined by Chalasani and Motwani in which, unlike their definition, C is part of the input: each vertex v of a graph G = (V, E) has a certain amount x(v) of a commodity and wishes to have an amount equal to y(v) (we assume that Sigma(v is an element of V) x(v) = Sigma(v is an element of V) y(v) and all quantities are assumed to be integers);given a vehicle of capacity C, find a minimal route that balances all vertices, that is, that allows to have an amount y(v) of the commodity on each vertex v. This paper presents among other things complexity results, lower bounds, approximation algorithms, and a polynomial algorithm when G is a tree.
The translocation operation is one of the popular operations for genome rearrangement. In this paper, we present a algorithm for computing unsigned translocation distance which improves upon the best known 2-approxima...
详细信息
The translocation operation is one of the popular operations for genome rearrangement. In this paper, we present a algorithm for computing unsigned translocation distance which improves upon the best known 2-approximation algorithm [J. Kececioglu, R. Ravi, Of mice and men: algorithms for evolutionary distances between genomes with translocation, in: 6th ACM-SIAM Symposium on Discrete algorithms, 1995, pp. 604-6131. (c) 2007 Elsevier Inc. All rights reserved.
When a link or node fails in a network, the affected flows are automatically rerouted. This increases the hop counts of the flows, which can drastically degrade network performance. Keeping the hop lengths as stable a...
详细信息
When a link or node fails in a network, the affected flows are automatically rerouted. This increases the hop counts of the flows, which can drastically degrade network performance. Keeping the hop lengths as stable as possible, i.e., minimizing the difference in hop length between the original flow and the rerouted flow is important for network reliability. Therefore, network service providers need a method for designing networks that stabilizes the flow hop length and maintains connectivity during a link or node failure with limited investment cost. First, we formulate the network design problem used for determining the set of links to be added that satisfies the required constraints on flow hop length stability, connectivity, and node degree. Next, we prove that this problem is NP-complete and present two approximation algorithms for the optimization problem so as to minimize the number of links added. Evaluation of the performance of these algorithms by using 39 backbone networks of commercial ISPs and networks generated by two well-known models showed that the proposed algorithms provide effective solutions in sufficiently short computation time.
暂无评论