1. 주 제 : Quadratization of Pseudo-Boolean Functions

2. 연 사 : Professor Endre Boros (Rutgers University)


■ Short Bio :
        Endre Boros is a Distinguished Professor of the Department of Management Science and Information Systems and Director of the Operations Research Center (RUTCOR). 
        His research interests include graph theory, combinatorial optimization, theory of Boolean functions, game theory, machine learning, data mining, and their applications. 
        He published over 190 articles in refereed journals and conference proceedings, edited 18 volumes, and authored a book chapter on Horn functions and their applications. 
        He is a Foreign Member of the Hungarian Academy of Sciences. He serves as the Editor-in-Chief of the Annals of Operations Research and Discrete Applied Mathematics; and as an Associate Editor for the Annals of Mathematics and Artificial Intelligence, for Discrete Optimization, and member of the editorial boards of numerous other international journals.


3. 내 용 : The problem of minimizing a pseudo-Boolean function (over the set of binary vectors) appears to be the common form of numerous optimization problems, including the well-known MAX-SAT and MAX-CUT problems, and have applications in areas ranging from physics through chip design to computer vision, etc.

               Some of these applications lead to the minimization of a quadratic pseudo-Boolean function, and hence such quadratic binary optimization problems received ample attention in the past decades. One of the most frequently used technique is based on roof-duality, and aims at finding in
polynomial time a simpler form of the given quadratic minimization problem, by fixing some of the variables at their provably optimum value (persistency) and decomposing the residual problem into variable disjoint smaller subproblems.

               In many applications of pseudo-Boolean optimization, in particular in vision problems, the objective function is a higher degree multilinear polynomial. For such problems there are substantially fewer effective techniques available. In particular, there is no analogue to the persistencies (fixing variables at their provably optimum value) provided by roof-duality for the quadratic case. On the other hand, more and more applications would demand efficient methods for the minimization of such higher degree pseudo-Boolean functions. This increased interest, in particular in the computer vision community, lead to a systematic study of methods to reduce a higher degree minimization problem to a quadratic one. We report on the most recent techniques and the computational success of

4. 일 시 : 2016년 10월 28일 (금) 오후 4시 반 - 5시 반

5. 장 소 : 39동  325호

6. 문 의 : 이경식교수 (optima@snu.ac.kr)