Minimum deviation and balanced optimization: A unified approach

Most combinatorial optimization problems have as criterion the sum of the weights in a solution, but sometimes the criterion is different. A Minimum Deviation Problem minimizes the difference between maximum and average weight in a solution. The authors introduce a general solution scheme that is also suited for balanced optimization, i.e., the problem to find a solution that has a minimal deviation between the largest and the smallest weight. The scheme has a forward and a backward version, that gives more flexibility to improve complexity results. The authors analyze the approach for spanning trees, paths and Steiner trees in graphs.