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.