Search

Abstract: The inverse optimization problem is to modify the weight (or cost, length, capacity and so on) such that a given feasible solution becomes an optimal solution. In this paper, we consider the inverse min–max spanning tree problem under the weighted sum-type Hamming distance. For the model considered, we present its combinatorial algorithm that runs in strongly polynomial times. [Copyright &y& Elsevier]

Abstract: Since 1989 when Melen and Turner introduced an elegant model for interconnection networks that carry multirate traffic, the theory and applications of the three-stage Clos network has been extended from circuit switching to the multirate environment. Chung and Ross conjectured that is rearrangeable if each call has weight chosen from a given set of weights. Lin et al. confirmed the conjecture for a restricted discrete bandwidth case only. In this paper we show that the conjecture of Chung and Ross holds not only in the discrete bandwidth case but also in the continuous bandwidth case for . [Copyright &y& Elsevier]

The optimization versions of the k-PARTITIONING problems are considered in this paper. For the objective to maximize the minimum load of m subsets, we first show that the FOLDING algorithm has a tight worst case ratio of max{2/k,1/m}. Then, we present an algorithm called HARMONIC1 with a worst case ratio at least max{ 1/k, 1/(⌈Σi=1m 1/i ⌉ +1)}. It concludes the HARMONIC1 is better than FOLDING for k > 2(⌈ Σi=1m 1/i ⌉ + 1). We further show that HARMONICI is asymptotically optimal ordinal algorithm. We also present an algorithm HARMONIC2 for solving the general κi-PARTITIONING problem. [Copyright &y& Elsevier]