Search

Given an undirected network G( V, E, c) and a perfect matching M, the inverse maximum perfect matching problem is to modify the cost vector as little as possible such that the given perfect matching M can form a maximum perfect matching. The modification can be measured by different norms. In this paper, we consider the weighted inverse maximum perfect matching problems under the Hamming distance, where we use the weighted Hamming distance to measure the modification of the edges. We consider both of the sum-type and the bottleneck-type problems. For the general case of the sum-type case, we show it is NP-hard. For the bottleneck-type, we present a strongly polynomial algorithm which can be done in O( m · n). [ABSTRACT FROM AUTHOR]

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]

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]