ϵ-optimization schemes and L-bit precision: Alternative perspectives for solving combinatorial optimization problems

Motivated by the need to deal with imprecise data in real-world optimization problems, we introduce two new models for algorithm design and analysis. The first model, called the L-bit precision model, leads to an alternate concept of polynomial-time solvability. Expressing numbers in L-bit precision reflects the format in which large numbers are stored in computers today. The second concept, called ϵ-optimization, provides an alternative approach to approximation schemes for measuring distance from optimality. In contrast to the worst-case relative error, the notion of an ϵ-optimal solution is invariant under subtraction of a constant from the objective function, and it is properly defined even if the objective function takes on negative values.