ε-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. Besides discussing the relation between these two models and preexisting concepts, we focus on designing polynomial-time algorithms for solving NP-hard problems in which some or all data are expressed with L-bit precision, and on designing fully polynomial-time ε-optimization schemes for NP-hard problems, including some that do not possess fully polynomial-time approximation schemes (unless P=NP).