εε-optimization schemes and LL-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 LL-bit precision model, leads to an alternate concept of polynomial-time solvability. Expressing numbers in LL-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 LL-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).