Bilkent University
Department of Computer Engineering
S E M I N A R
Risk Analysis and Partial Vertex Cover in Bipartite Graphs
Dr. Buğra Çaşkurlu
West Virginia University
We introduce a real-time risk management model to protect a system by reducing its functionality temporarily when it is under siege. Instead of statically configuring a system, we propose to monitor the risk level, and use it to drive the tradeoff between security and usability. Our goal is to minimize the tension between security and usability of the system by trading them dynamically. The advantage of this approach is that it provides users the maximum possible functionality for any predefined level of risk tolerance. In this talk, we first present our comprehensive risk management model, and show that algorithmic underpinnings of optimal risk management can be formulated as the Partial Vertex Cover (PVC) problem in bipartite graphs.
Though the Vertex Cover problem is known to be polynomial-time computable in bipartite graphs, the computational complexity of the PVC problem is open in bipartite graphs and there is no known approximation algorithm with an approximation factor smaller than 2. In this talk, we will show that the PVC problem is strongly NP-hard in bipartite graphs and provide a 1.708-approximation algorithm. At the end of the talk, we will discuss several open problems and interesting future research directions.
Bio: Dr. Bugra Caskurlu received his B.S. degree in Computer Engineering from Bilkent University in 2003. After his graduation, he started his graduate studies at Rensselaer Polytechnic Institute and received his M.S. and Ph.D. degrees in Computer Science in 2006 and 2010, respectively. Since 2010, he has been working as research associate in the Computer Science and Electrical Engineering department of West Virginia University. His research interests are Algorithmic Game Theory, Approximation Algorithms, Graph Theory and Systems Modeling. In the scientific community, he is known for his contributions to Network Creation Games and Game Theoretic Solution Concepts.
DATE: 28 May, 2012, Monday @ 13:40
PLACE: EA409