In Williamson and Shmoys' textbook The Design of Approximation Algorithms they make the following assumption: We assume that there is some objective function mapping each possible solution of an optimization problem to some nonnegative value...Vazirani makes the same assumption:Each valid instance...comes with a nonempty set of feasible solutions, each of which is assigned a nonnegative rational number called its objective function value.What if my objective function can take negative values? Is there a standard way to deal with this? What if it is known that $-1$ is a lower bound?
Approximation factor when objective can be negative
approximation algorithms