ε-optimization schemes and L-bit precision: Alternative perspectives in combinatorial optimization (extended abstract)

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 polynomialtime algorithms for solving NP-hard problems in which some or all of the data is expressed with L-bit precision, and on designing fully polynomial-time ε-optimization schemes for NP-hard problems including those that do not possess fully polynomial-time approximation schemes, unless P = NP.