Search

In the demand routing and slotting problem on unit demands (unit-DRSP), we are given a set of unit demands on an n-node ring. Each demand, which is a (source, destination) pair, must be routed clockwise or counterclockwise and assigned a slot so that no two routes that overlap occupy the same slot. The objective is to minimize the total number of slots used. It is well known that unit-DRSP is NP-complete. The best deterministic approximation algorithm guarantees a solution that is 2 × OPT. A demand of unit-DRSP can be viewed as a chord on the ring. Let w denote the size of the largest set of demand chords that mutually cross in the interior of the ring. We present a simple approximation algorithm that uses at most (2 - 1/[w/2]) × OPT slots in an n-node network; this is the first deterministic approximation algorithm that beats the factor of 2 for all values of OPT and therefore for all instances of the input. If randomization is allowed, an algorithm by Kumar produces, with high probability, a solution that uses asymptotically (1.5 + 1/2e + o(1)) × OPT slots. However, when OPT is not large enough, the factor can exceed 2. In this paper, we show how combining our algorithm with Kumar's yields a randomized approximation algorithm that has, with high probability, a constant factor of 2 1/θ(log n). While asymptotically it is not better than Kumar's, the approximation factor holds for all values of OPT. [ABSTRACT FROM AUTHOR]

Abstract: For a fixed family of graphs, an -packing in a graph is a set of pairwise vertex-disjoint subgraphs of , each isomorphic to an element of . Finding an -packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just . In this paper we provide new approximation algorithms and hardness results for the -packing problem where . We show that already for the -packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed . For we obtain better approximations. For we obtain a simple -approximation, achieving a known ratio that follows from a more involved algorithm of Halldórsson. For , we obtain a -approximation, and for we obtain a -approximation. [Copyright &y& Elsevier]

A procedure is given for approximating the equilibrium behavior of multi-server loss systems having distinguishable servers and multiple customer types under light to moderate traffic intensity. Calls are assumed to arrive according to independent Poisson processes for each customer type. General service time distributions which may depend on both server and customer type are allowed. For N servers, the approximation routine consists of a simple iterative procedure in N nonlinear equations. Computational experience with respect to the convergence properties of the iteration and the accuracy of the approximation is given. [ABSTRACT FROM AUTHOR]

We consider the bicriterion multimodal assignment problem, which is a new generalization of the classical linear assignment problem. A two-phase solution method using an effective ranking scheme is presented. The algorithm is valid for generating all nondominated criterion points or an approximation. Extensive computational results are conducted on a large library of test instances to test the performance of the algorithm and to identify hard test instances. Also, test results of the algorithm applied to the bicriterion assignment problem are provided. [ABSTRACT FROM AUTHOR]