I've got a question about how best to classify the performance of an approximate algorithm. I'm trying to find the 'correct' value of a graph problem instance whose cost function has an objective function and a penalty function. I've configured my method such that the optimum solution of the problem has the highest value, fulfilling the objective criterion adds to the cost function value, and the penalty subtracts from it. This means that some poor solutions have negative values.

Typically the performance of an approximate algorithm is measured as:

$ \frac{C_{i}}{C_{max}} = r $.

I'm a little confused where to set my baseline of $0$ however. Should I translate my objective values such that they are all positive, and so add the $ |{\min C}|$ to all my cost function values and the best possible solution? Or is it best practise to calculate $r$ as found ?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.