Balanced optimization problems |
| |
Authors: | S Martello W.R Pulleyblank P Toth D de Werra |
| |
Affiliation: | University of Bologna, Italy;University of Waterloo, Canada;University of Bologna, Italy;Federal Institute of Technology, Lausanne, Switzerland |
| |
Abstract: | Suppose we are given a finite set E, a family F of ‘feasible’ subsets of E and a real weight c(e) associated with every e?E. We consider the problem of finding S?F for which max {c(e)?c(e′): e, e′ ?S} is minimized. In other words, the differenc value between the largest and smallest value used should be as small as possible. We show that if we can efficiently answer the feasibility question then we can efficiently solve the optimization problem. We specialize these results to assignment problems and thereby obtain on O(n4) algorithm for ‘balanced’ assignment problems. |
| |
Keywords: | combinatorial optimization balancing computational complexity assignment problem matching problem |
本文献已被 ScienceDirect 等数据库收录! |