MINIMUM DISPERSION PROBLEMS

We consider the problem of identifying a feasible solution S under a g eneral combinatorial optimization setting such that the sum of the abs olute deviation of element weights associated with S from the median o f the element weights of S is as small as possible (MADM). It is shown that MADM can be solved in polynomial time whenever an associated min sum problem can be solved in polynomial time. If this minsum problem i s difficult, but permits an epsilon-approximation scheme, then MADM ca n also be solved by an epsilon-approximation scheme. We also consider the case when median is replaced by average (MADA). Unlike MADM, MADA is NP-hard even if the associated minsum problem is solvable in polyno mial time. Further, we consider MADLP, the linear programming analog o f MADM. MADLP is formulated as a linear program with an exponential nu mber of constraints and a polynomial time algorithm is proposed to sol ve it.