current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite

Hi I am looking for an approximation algorithm for 0-1 integer linear programming. Currently the approximation algorithms I find need to relax the interval to be [0,1]. However, my problem can only treat 0 or 1 as the solution.

Does anyone have ideas? Thank you in advance.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

The classic procedure to obtain an integral solution would be branch-and-bound. If this is not what you are looking fore, provide more details.

share|improve this answer
    
Hi Chris, the branch-and-bound is right for me. I examined an example of branch-and-bound. The time complexity of 0-1 case seems to be exponential. Am I right? Do you know some approximation algorithms with smaller time complexity? –  user811416 Feb 21 '13 at 5:07
1  
that is true for the worst case. But the performance of branch and bound depends on several aspects, for example the branching rules or if the primal and dual bounds are good. These influence, how large the search tree becomes. –  Chris Feb 21 '13 at 8:13
    
OK. Thank you again. –  user811416 Feb 21 '13 at 9:42

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.