An Epsilon-Approximation Scheme for Minimum Variance Combinatorial Problems

Katoh, N. (1987). An Epsilon-Approximation Scheme for Minimum Variance Combinatorial Problems. IIASA Working Paper. IIASA, Laxenburg, Austria: WP-87-117


Download (536kB) | Preview


Suppose that we are given a finite set E, a family of feasible subsets of E and an integer cost associated with each element in E. The author considers the problem of finding a feasible subset such that the variance among the costs of elements in the subset is minimized. The author shows that if one can solve the corresponding minimum cost problem in polynomial time, it is possible to construct a fully polynomial time approximation scheme for the above minimum variance problem.

Item Type: Monograph (IIASA Working Paper)
Research Programs: Methodology of Decision Analysis (MDA)
System and Decision Sciences - Core (SDS)
Depositing User: IIASA Import
Date Deposited: 15 Jan 2016 01:57
Last Modified: 27 Aug 2021 17:12

Actions (login required)

View Item View Item

International Institute for Applied Systems Analysis (IIASA)
Schlossplatz 1, A-2361 Laxenburg, Austria
Phone: (+43 2236) 807 0 Fax:(+43 2236) 71 313