1
안녕하세요, 저는 0-1 정수 선형 프로그래밍에 대한 근사 알고리즘을 찾고 있습니다. 현재 내가 발견 한 근사 알고리즘은 간격을 [0,1]로 완화해야합니다. 그러나, 내 문제는 단지 0 또는 1 솔루션으로 취급 할 수 있습니다.0-1 선형 선형 프로그래밍 근사 알고리즘
아이디어가 있습니까? 미리 감사드립니다.
A
답변
2
통합 솔루션을 얻는 고전적인 절차는 분기 별 바인딩입니다. 이것이 당신이 바라는 바가 아니라면, 더 자세한 내용을 제공하십시오.
관련 문제
- 1. numpy의 로컬 선형 근사
- 2. 선형 프로그래밍?
- 3. 선형 패턴 일치를위한 알고리즘?
- 4. C에서 선형 증가 알고리즘
- 5. 선형 정렬 알고리즘
- 6. 윤곽을 채우기위한 선형 알고리즘
- 7. 선형 방정식에 대한 빠른 근사 솔루션?
- 8. 선형 프로그래밍 - MATLAB
- 9. matlab에는, 선형 프로그래밍
- 10. GLPK 선형 프로그래밍
- 11. 선형 프로그래밍 운송 최적화
- 12. MapReduce 선형 프로그래밍
- 13. 정수 선형 프로그래밍
- 14. 선형 프로그래밍 모델
- 15. 선형 적으로 증가하는 암흑 알고리즘
- 16. 선형 피드백 시프트 레지스터 알고리즘
- 17. 선형 시간에 배열을 정렬하는 알고리즘
- 18. 이미 선형 시간 알고리즘 병렬화
- 19. 하스켈 선형 시간 온라인 알고리즘
- 20. 그래프 알고리즘, 근사 알고리즘
- 21. 선형 레이아웃을 안드로이드에 프로그래밍 방식으로 다른 선형 레이아웃을 넣는 방법
- 22. 테스트 커버 용 선형 선형 프로그래밍 공식? 다음과 같이
- 23. 정규 표현식을 선형 문법으로 변환하는 알고리즘
- 24. 선형 프로그래밍 MATLAB에 의해 해결할
- 25. iOS 용 선형 프로그래밍 라이브러리
- 26. 프롤로그로 선형 프로그래밍 문제 해결
- 27. 정수 선형 프로그래밍 + 파이썬 + 우분투
- 28. MKP에 대해 편평한 선형 프로그래밍
- 29. 선형 적으로 선형 레이아웃 정의하기
- 30. 선형 레이아웃을 허용하는 빠른 알고리즘/데이터 구조?
Chris 안녕하세요, 지점과 경계가 제게 적합합니다. 나는 [가지와 경계의 예] (http://wps.prenhall.com/wps/media/objects/1159/1186960/cdrom_modules/module_c.pdf)를 검토했다. 0-1 사건의 시간 복잡도는 기하 급수적 인 것 같습니다. 내가 맞습니까? 작은 시간 복잡도를 가진 근사 알고리즘을 알고 있습니까? – user811416
은 최악의 경우에 해당합니다. 그러나 브랜치와 바운드의 성능은 여러 가지 측면, 예를 들어 브랜칭 규칙이나 기본 및 이중 경계가 양호한 지 여부에 따라 달라집니다. 이러한 영향은 검색 트리가 얼마나 커지는지를 나타냅니다. – Kalle
확인. 다시 감사합니다. – user811416