DIMACS TR: 95-08
Optimization under Ordinal Scales: When is a Greedy Solution
Optimal?
Author: Aleksandar Pekec
ABSTRACT
Mathematical formulation of an optimization problem often depends on
data which can be measured in more than one acceptable way. If the
conclusion of optimality depends on the choice of measure, then we
should question whether it is meaningful to ask for an optimal
solution. If meaningful optimal solution exists and the
objective function depends on data measured on an ordinal scale of
measurement, then the greedy algorithm will give such a solution for
a wide range of objective functions.
Keywords: Optimization, Measurement Theory, Greedy Algorithms
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-08.ps.gz
DIMACS Home Page