We usually evaluate approximation algorithms by the ratio of the output value to the unknown optimal value. Although it is almost a dogma at this point that this is the most reliable way to evaluate an algorithm, the last issue of the New York Review of Books gives an outstanding counterexample.
The article is debunking a disinformation piece published by 16 scientists in the Wall Street Journal on January 27. The WSJ misleading article was a piece of global warming skepticism.William Nordhaus establishes the fallacy of their arguments one by one. The point that caught my attention was the one about economic analysis. Nordhaus writes: The sixteen scientists argue, citing my research, that economics does not support policies to slow climate change in the next half-century, then moves on to offer the following, which can be interpreted as a beautifully clear argument against making a dogma out of approximation ratios.
The authors cite the “benefit-to-cost ratio” to support their argument. Elementary cost-benefit and business economics teach that this is an incorrect criterion for selecting investments or policies. The appropriate criterion for decisions in this context is net benefits (that is, the difference between, and not the ratio of, benefits and costs).
This point can be seen in a simple example, which would apply in the case of investments to slow climate change. Suppose we were thinking about two policies. Policy A has a small investment in abatement of CO2 emissions. It costs relatively little (say $1 billion) but has substantial benefits (say $10 billion), for a net benefit of $9 billion. Now compare this with a very effective and larger investment, Policy B. This second investment costs more (say $10 billion) but has substantial benefits (say $50 billion), for a net benefit of $40 billion. B is preferable because it has higher net benefits ($40 billion for B as compared with $9 for A), but A has a higher benefit-cost ratio (a ratio of 10 for A as compared with 5 for B). This example shows why we should, in designing the most effective policies, look at benefits minus costs, not benefits divided by costs.
No offense, but I don't see what this has to do with approximation ratios, where one measures the cost of an algorithm's solution versus the optimal cost; one reason it is useful is that it is invariant under scaling. Measuring benefits versus costs is something different altogether, and it's certainly not invariant under scaling.
ReplyDeleteI understand, but scale invariance might not be desirable for all optimization problems. No?
ReplyDelete