Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I have also encountered the phrase "[...]designing a fractional algorithm and transforming it into a discrete algorithm [...]". Could the word "fractional" mean "continuous"? –  George Ts May 2 at 22:56
    
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 –  Mohsen May 3 at 9:44
    
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. –  vzn May 3 at 14:58

1 Answer 1

up vote 10 down vote accepted

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'.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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