Often, in a lot of texts concerning approximation algorithms I see the following notation (for example, here in page 19 of the PDF or the first page of the introduction):

... and a cost function on vertices $c:V\to \mathbf{Q}^+$ ...

Is this just the positive rationals? Or is this something else?


I'm going to say yes, positive rationals, because:

  • That's what it means throughout math literature.
  • That's a sensible domain for a cost function. It would possibly be a different algorithm problem if "negative" cost were legal. Furthermore real numbers introduce questions of representation and comparing them, so while mathematicians or economists often consider real numbers for quantity, computer scientists are more cautious.
  • There is no front or back matter indicating otherwise.
| cite | improve this answer | |
  • $\begingroup$ I agree but what does "positive" mean? Half the world says "positive" for $x\geq 0$ and "strictly positive" for $x>0$; the other half says "nonnegative" for $x\geq 0$ and "positive" for $x>0$. (Which is why I prefer to write $\mathbb{Q}_{\geq 0}$ or $\mathbb{Q}_{> 0}$; or superscripts, if you prefer.) $\endgroup$ – David Richerby Sep 29 '16 at 9:17
  • 1
    $\begingroup$ @DavidRicherby I've never heard "positive" to mean "nonnegative" in my life. If the author uses it that way, send in an erratum. $\endgroup$ – djechlin Sep 29 '16 at 14:31

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.