סמינר מחלקתי

Privacy-Preserving Algorithms for Distributed Constraint Optimization

Prof. Tamir Tassa - Department of Mathematics and Computer Science, The Open University

Abstract:

Distributed Constraint Optimization Problems (DCOPs) provide a powerful framework that can naturally represent many combinatorial problems that are distributed by nature. In such problems there is a set of agents, where each one holds some variables that can take values in corresponding domains. Some combinations of value assignments incur a cost to the agents that hold the corresponding variables. The agents wish to assign values to their variables so that the total cost which that assignment incurs would be minimal. Many algorithms were proposed in the past decade for solving DCOPs, which are NP-hard. However, very few studies so far considered the need to preserve private information when solving those problems. Such private information includes the cost of value assignments, the combinations of assignments that incur costs, the finally selected assignment, or even the identity of the interacting agents. In this talk we present and discuss privacy-preserving variants of two fundamental DCOP algorithms – SyncBB (Synchronous Branch and Bound) and Max-Sum.

Joint work with Tal Grinshpoun and Roie Zivan 

ההרצאה תתקיים ביום שלישי 21.4.15, בשעה 14:00 בחדר 206, בנין וולפסון הנדסה, הפקולטה להנדסה, אוניברסיטת תל-אביב.