# Understanding (1+ ε) approximation when objective is discrete

Some problems in operations research have (1+ε) approximation algorithms which run in polynomial time. So we have an algorihm that produces a solution which is whose objective is within that factor (1+ε).

If the objective can only assume discrete values there might be no feasible solution but an optimal solution with an objective in [global_opt, global_opt * (1+ε)].

Since approximation algorithms return a feasible solution to the problem they always find an optimal solution for instances where objectives can only assume discrete values and the second best discrete value is sufficiently far (atleast ε*global_opt) apart from the global optimium. Is that reasoning correct?

• That reasoning seems correct.
– prubin
Commented Mar 5 at 19:20
• If prubin wants to write that up as an answer then i can accept that. I'd also be interested in cases were rewriting the problem can push the second best solution further apart from the best solution that'd be an interesting addition to make me accept the answer from someone else too. Commented Mar 5 at 20:04
• What do you mean by "rewriting the problem"? I presume that you are assuming the optimal solution is unique. To increase the gap between best and second best answer, you would have to modify the model in a way that changes the set of feasible solutions.
– prubin
Commented Mar 6 at 4:07
• Actually, you are right. That doesn't make any sense, i thought dividing linear constraint by their GCD could do something like that but it doesn't. Commented Mar 6 at 12:43
• @worldsmithhelper Done!
– prubin
Commented Mar 8 at 17:25

I agree that if a $$(1+\epsilon)$$ approximate algorithm returns a feasible solution to a problem where the second best feasible solution (if there is one) has objective value differing from the optimum by a factor greater than $$\epsilon,$$ the algorithm's solution is optimal.

Unfortunately, given a problem where the second best objective value differs from optimum by less than a factor of $$\epsilon,$$ there is no way to "tweak" the model to increase the spacing in objective values without altering the feasible region (hence fundamentally changing the model). In particular, scaling the objective does not help since $$f' \le (1+\epsilon)f \implies \alpha f' \le \alpha (1+\epsilon)f$$ for any positive factor $$\alpha$$. Here I assume for convenience a minimization problem with optimal value $$f$$ and feasible value $$f'.$$

• Dear @prubin, maybe I am missing something. Suppose we have an PTAS with a ratio of ($1+\epsilon$). If this scheme can provide an approximate feasible solution then what is really the difference between this feasible solution and the second one? I mean why does it make sense to investigate the second feasible solution? Commented Mar 8 at 17:40
• @A.Omidi The issue is whether the first feasible solution is necessarily optimal. The ratio tells us it is "close" to optimal. If we somehow know that the problem does not have more than one solution (more accurately, more than one attainable objective value) that close to optimal, then the first solution is optimal.
– prubin
Commented Mar 8 at 18:51
• Dear @prubin, thank for the clarification. Would you please, is what you mentioned about more accurately, more than one attainable objective value an assumption or is a provabl lemma in an PTAS? Commented Mar 8 at 19:43
• As far as I see, at least in scheduling problems, when an algorithm is proven to be an PTAS or specifically FPTAS, the solution found by that is actually the best one rather than the optimal solution in an polynomial time and already rather than it's ratio on $\epsilon$. Since, is it possible to have an FPTAS and there exit a solution, say non-optimal, and the algorithm cannot find that? Commented Mar 8 at 19:55
• @A.Omidi Sorry, I cannot follow what you are saying.
– prubin
Commented Mar 8 at 21:12