3
$\begingroup$

What is the definition of the word "fractional" in algorithms? I have encountered the word in phrases like "fractional algorithm", "fractional node routing problem".

Note: English is not my native language

$\endgroup$
3
  • $\begingroup$ I have also encountered the phrase "[...]designing a fractional algorithm and transforming it into a discrete algorithm [...]". Could the word "fractional" mean "continuous"? $\endgroup$ – George Tseres May 2 '14 at 22:56
  • $\begingroup$ Suresh's answer is correct. See Chapter 11 of Vazirani's Approximation algorithms book for an example of such algorithms. The book is available at ceid.upatras.gr/webpages/courses/approx/book.pdf $\endgroup$ – Helium May 3 '14 at 9:44
  • $\begingroup$ there is also a sense of "fractional" wrt graphs referring to hypergraphs. use of the term presumably is broad and does not have a fully general crosscutting concept or definition. $\endgroup$ – vzn May 3 '14 at 14:58
10
$\begingroup$

The most common use of 'fractional' is when you're solving an integer program. You relax it by dropping the constraints that the solution be integers, thus yielding a linear program in which the variables can take fractional values (fractional comes from fraction). Later, you can convert the fractional values into integers via a process called 'rounding'.

$\endgroup$

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.