Correlation Decay and Deterministic Approximation Algorithms

*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************

Event Details
  • Date/Time:
    • Tuesday September 23, 2008 - Wednesday September 24, 2008
      3:00 pm - 3:59 pm
  • Location: Executive Classroom 228
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    $0.00
  • Extras:
Contact
Anita Race
H. Milton Stewart School of Industrial and Systems Engineering
Contact Anita Race
Summaries

Summary Sentence: Correlation Decay and Deterministic Approximation Algorithms

Full Summary: Correlation Decay and Deterministic Approximation Algorithms

TITLE: Correlation Decay and Deterministic Approximation Algorithms

SPEAKER: Dr. Prasad Tetali

ABSTRACT:

The notion of a correlation decay, originating in statistical physics, has recently played an important role in yielding deterministic approximation algorithms for various counting problems. I will try to illustrate this technique with two examples: counting matchings in bounded degree graphs, and counting independent sets in certain subclasses of claw-free graphs.

Additional Information

In Campus Calendar
No
Groups

School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
Categories
Seminar/Lecture/Colloquium
Keywords
Approximation Algorithms, Correlation Decay
Status
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Oct 12, 2009 - 4:38pm
  • Last Updated: Oct 7, 2016 - 9:47pm