본문 바로가기
HOME> 보고서 > 보고서 검색상세

보고서 상세정보

석박사 모험연구 프로그램 운영

  • 주관연구기관

    한국과학기술원
    Korea Advanced Institute of Science and Technology

  • 보고서유형

    최종보고서

  • 발행국가

    대한민국

  • 언어

    대한민국

  • 발행년월

    2015-12

  • 주관부처

    미래창조과학부
    KA

  • 사업 관리 기관

    한국과학기술원
    Korea Advanced Institute of Science and Technology

  • 등록번호

    TRKO201600002224

  • 키워드

    Combinatorial optimization,Belief propagation,Parallel algorithm,Maximum weighted matching

  • DB 구축일자

    2016-06-04

  • 초록 


    Graphical Model (GM) has provided a popular framework for big data analytics because it often lends itself to distributed and par...

    Graphical Model (GM) has provided a popular framework for big data analytics because it often lends itself to distributed and parallel processing by utilizing graph-based 'local' structures. It models correlated random variables where 1n particular, the max-product Belief Propagation (BP) is the most popular heuristic to compute the mos t-likely assignment in GMs.
    In the past years, it has been proven that BP can solve a few classes of combinatorial optimization problems under certain conditions. Motivated by this. we explore the prospect of using BP to solve generic combinatorial optimization problems. The challenge is that, in practice, BP may converge very slowly and even if it does converge, the BP decision often violates the constraints of the original problem. This paper proposes a generic framework that enables us to apply BP-based algorithms to compute an approximate feasible solution for an arbitrary combinatorial optimization task. The mam novel ingredients include (a) careful initialization of BP messages, (b) hybrid damping on BP updates, and (c) post - processing using BP beliefs. Utilizing the framework, we develop parallel algorithms for several large- scale combinatorial optimization problems including maximum weight matching, traveling salesman, vertex cover and independent set. We demonstrate that our framework delivers high approximation ratio, speeds up the process by parallelization, and allows large-scale processing involving billions of variables.


    ...


  • 목차(Contents) 

    1. COVER ... 1
    2. 제출문 ... 2
    3. 보고서 초록 ... 3
    4. SUMMARY ... 4
    5. 목차 ... 5
    6. I. Introduction ... 6
    7. II. Preliminaries ... 9
    8. III. Algorithm Design ... 11
    9. IV....
    1. COVER ... 1
    2. 제출문 ... 2
    3. 보고서 초록 ... 3
    4. SUMMARY ... 4
    5. 목차 ... 5
    6. I. Introduction ... 6
    7. II. Preliminaries ... 9
    8. III. Algorithm Design ... 11
    9. IV. Parallel Design And Implementation ... 14
    10. A. Asynchronous Message Update ... 14
    11. B. Local Post-Processing ... 15
    12. C. Parallel Implementation ... 15
    13. V. Evaluation ... 17
    14. A. Exporiment Setup ... 17
    15. B. Approximation Ratio ... 18
    16. C. Parallelization Speed-up ... 19
    17. D. Large-scale Optimization ... 20
    18. VI. Conclusion ... 21
    19. End of Page ... 22
  • 참고문헌

    1. 전체(0)
    2. 논문(0)
    3. 특허(0)
    4. 보고서(0)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역