2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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.
Improve this answer
$\endgroup$
2
  • $\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
    Commented Sep 29, 2016 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
    Commented Sep 29, 2016 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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