ACM Chennai - January 2011 Invited Lecture and Chapter Meeting

ACM Chennai - January 2011 Invited Lecture and Chapter Meeting

 

  • Free Registration

    Sale Date Ended

    0
    Sold Out

Invite friends

Contact Us

Page Views : 1113

About The Event

Speaker - Dr. Venkatesh Raman, MatScience

Title - NP-complete problems and approaches to deal with them

Abstract - It was exactly 40 years ago that Cook and Levin proved their famous theorem that the Satisfiability problem in logic does not have an efficient (polynomial time) algorithm unless several other similar problems have one. This led to the development of the important notion of intractability and the NP-completeness theory. Whether NP-complete problems have polynomial time algorithms continues to be one of the major open problems in Computer Science. In the last forty years researchers have discovered that a number of ptimization problems related to scheduling, VLSI and several other domains are NP-complete and hence can not have an efficient way of exactly solving them. In this talk we will look at approaches that have been developed in the last several years to address this issue. Some of the approaches we will look at include approximation, randomization and parameterization. Date - Saturday, Jan 22, 2011 Agenda - 4 - 5:30 PM Talk 6 - 7 PM Chapter Meeting Venue - Ramanujan Auditorium, MatScience, Taramani Directions to the venue - http://www.imsc.res.in/getting_imsc

Venue Map