Correlation Decay and Deterministic Approximation Algorithms

Event Details
  • Date/Time:
    • Tuesday September 23, 2008
      3:00 pm - 4:00 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

H. Milton Stewart 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