Wayne State University

 
Add An Event
TODAYThursday - Jun 20, 2013
Day | Week | Month | Date Range
Right OCTOBER 2012 Right
SU M TU W TH F SA
30123456
78910111213
14151617181920
21222324252627
28293031123

College of Engineering

"Minimizing Movement: Approximability and Fixed Parameter Tractability" Department of Computer Science Graduate Seminar Series
October 2, 2012 | 3:00pm - 4:00pm
Print Save to iCal
Share a Photo Share a Video
Report a Problem
Category: Seminar
Location: Purdy/Kresge Library #110 | Map
5265 Cass
Detroit, MI 48202
Cost: Free
Calendars: Main Events Calendar, Computer Science, College of Engineering



Graduate Seminar Series featuring Dr. Mohammad Hajiaghayi Oct 2nd at 3pm

Having trouble viewing? View Online

College of Engineering - Computer Science

SEMINAR ANNOUNCEMENT

October 2, 2012 3:00pm – 4:00pm, Purdy-Kresge Library Room 110

MINIMIZING MOVEMENT:
APPROXIMABILITY AND FIXED PARAMETER TRACTABILITY

Dr. Mohammad T. Hajiaghayi

Jack and Rita G. Minker Associate Professor of Computer Science
University of Maryland

Abstract
Mohammad HajiaghayiWe study an extensive class of movement minimization problems which arise from many practical scenarios but so far have little theoretical study. This general family of movement problems encompass an intriguing range of graph and geometric algorithms, with several real-world applications and a surprising range of approximability and fixed-parameter tractability. These problems involve planning the coordinated motion of a collection of agents (representing robots, people, map labels, network messages, etc) to achieve a global property in the network while minimizing the maximum or average movement (expended energy). Given that the number of mobile agents is typically much smaller than the complexity of the environment, we turn to fixed-parameter tractability. We characterize the boundary between tractable and intractable movement problems in a very general set up and fortunately show that many movement problems of interest can be solved efficiently. On the other hand, we give approximation algorithms and inapproximability results for some classes of movement problems. In some cases, we obtain tight approximation and inapproximability results assuming P! = NP.
Bio
Dr. Mohammad T. Hajiaghayi is the Jack and Rita G. Minker Associate Professor of Computer Science at the University of Maryland with a joint appointment in the University's Institute for Advanced Computer Studies (UMIACS). In addition, he holds a Research Affiliate position in MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) and is a Permanent Member of Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers. Before joining the University of Maryland, he was a Senior Researcher in the Algorithms and Theoretical Computer Science group at AT&T Labs-- Research to which he is still a consultant. Before that, he was a one-year Postdoctoral Fellow in the School of Computer Science at Carnegie Mellon University (with ALADDIN project) and a one-year Postdoctoral Associate in MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) from which he also earned his Ph.D. in 2005. During his Ph.D. studies, he spent some time at IBM Research centers and Microsoft Research centers. Dr. Hajiaghayi got his M.Sc. in Computer Science from the University of Waterloo in 2001 and his B.Sc. in Computer Engineering from Sharif University of Technology in 2000.
Dr. Hajiaghayi's research interests are algorithmic game theory and combinatorial auctions, network design, combinatorial optimizations and approximation algorithms, fixed-parameter algorithms, algorithmic graph theory, distributed and mobile computing, and computational geometry and embeddings. In the course of his professional career in these areas, he has published more than 110 papers in top conferences and journals of computer science, won a few best paper awards, and served in program committees or editorial boards of several well-known international conferences and journals. He has received an NSF CAREER Award in 2010, a Google Faculty Research Award in 2010, an ONR Young Investigator Award in 2011, and the University of Maryland Research and Scholarship Award (RASA) in 2011. He won best paper awards at the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2010, the International Symposium on Algorithms and Computation (ISAAC) 2006, and the Robocup 2001 Conference.
Wayne State University Aim Higher
For more information about this event, please contact Dennis Schwartz at 313-577-2477 or dschwartz@wayne.edu.