[Theory-local] CATS talk, , "wednesday oct 29th" , "11 am", AVW 4185 (fwd)

Article View: csd.grad

Article #91

#91

From: Samir Khuller
Date: Wed, 29 Oct 2008 01:12

40 lines
3492 bytes

---------- Forwarded message ----------
Date: Mon, 27 Oct 2008 22:24:45 -0400 (EDT)
From: malekian@cs.umd.edu
To: theory-local@cs.umd.edu
Subject: [Theory-local] CATS talk, , "wednesday oct 29th" , "11  am", AVW 4185

Event: Cats Talk
Speaker: Lap Chi Lau
Date: October 29th ( "Wednesday")
Time: "11 am"
Location: AVW 4185
Title: Iterative relaxation

ABSTRACT

In this talk we will present an iterative relaxation method to analyze
linear programming formulations of combinatorial optimization problems.
This method was first developed to tackle degree-bounded network design
problems, where it gave approximation algorithms with only additive
constant errors. In particular, it gave an approximation algorithm with
error at most 1 for the minimum bounded degree spanning tree problem,
proving a conjecture of Goemans. Then we will discuss how this method
provides new proofs of exact linear programming formulations for classical
problems, and see how these new proofs lead to new results in
approximation algorithms. Finally we will discuss potential future
directions of this method, and highlight some interesting open problems.
This iterative relaxation method is an extension of Jain's iterative
rounding method. We will start this talk with Jain's method and the
necessary background.

Joint work with T. Kiraly, J. Naor, M. Salavatipour, R. Ravi, and M. Singh.

_______________________________________________
Theory-local mailing list
Theory-local@mcfeely.cs.umd.edu
https://mailman.cs.umd.edu/mailman/listinfo/theory-local

Technical Details

Message-ID: <mailman.24.1225242723.3898.gradlist@mcfeely.cs.umd.edu>

Path:

arc1-ca.pugleaf.net!g2news1.google.com!news4.google.com!feeder.news-service.com!feeder.news-service.com!border1.nntp.ams.giganews.com!nntp.giganews.com!uio.no!elk.ncren.net!dailyplanet.umd.edu!not-for-mail

Show Full Headers

Complete Article Headers

X-Google-Thread: 10f4d5,b567e4bd0fde003b,start
X-Google-Attributes: gid10f4d5,domainid0,public,usenet
X-Google-Language: ENGLISH,ASCII-7-bit
Path: arc1-ca.pugleaf.net!g2news1.google.com!news4.google.com!feeder.news-service.com!feeder.news-service.com!border1.nntp.ams.giganews.com!nntp.giganews.com!uio.no!elk.ncren.net!dailyplanet.umd.edu!not-for-mail
From: Samir Khuller <samir@cs.umd.edu>
Newsgroups: csd.grad
Subject: [Theory-local] CATS talk, , "wednesday oct 29th" , "11  am", AVW
 4185 (fwd)
Date: Tue, 28 Oct 2008 21:12:01 -0400 (EDT)
Organization: University of Maryland College Park
Lines: 40
Message-ID: <mailman.24.1225242723.3898.gradlist@mcfeely.cs.umd.edu>
NNTP-Posting-Host: mcfeely.cs.umd.edu
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
X-Trace: dailyplanet.umd.edu 1225242724 22425 128.8.128.218 (29 Oct 2008 01:12:04 GMT)
X-Complaints-To: abuse@umd.edu
NNTP-Posting-Date: Wed, 29 Oct 2008 01:12:04 +0000 (UTC)
To: gradlist@cs.umd.edu, theory-local@cs.umd.edu
X-CSD-MailScanner-Watermark: 1225847522.04067@63MC1hRtjlbyQrEck/u3zg
X-CSD-MailScanner-Watermark: 1225847521.56686@A4+eBIAQUW+fdrqVhP0d0g
X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.0
 (tomato.cs.umd.edu [172.24.3.40]);
 Tue, 28 Oct 2008 21:12:01 -0400 (EDT)
X-BeenThere: gradlist@mcfeely.cs.umd.edu
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: CS Graduate Students <gradlist.mcfeely.cs.umd.edu>
List-Unsubscribe: <https://mailman.cs.umd.edu/mailman/listinfo/gradlist>,
 <mailto:gradlist-request@mcfeely.cs.umd.edu?subject=unsubscribe>
List-Archive: <https://mailman.cs.umd.edu/mailman/private/gradlist>
List-Post: <mailto:gradlist@mcfeely.cs.umd.edu>
List-Help: <mailto:gradlist-request@mcfeely.cs.umd.edu?subject=help>
List-Subscribe: <https://mailman.cs.umd.edu/mailman/listinfo/gradlist>,
 <mailto:gradlist-request@mcfeely.cs.umd.edu?subject=subscribe>