BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/664
DTSTAMP:20230914T125933Z
SUMMARY:Exact and Approximation Algorithms for Weighted Matroid  Intersecti
 on
DESCRIPTION:Speaker: Chien-Chung Huang (Chalmers University of Technology\n
 Department of Computer Science and Engineering\nSE-412 96 Gothenburg\nSwed
 en)\n\nAbstract: \nAbstract: We propose new exact and approximation algori
 thms for the weighted matroid intersection problem. Our exact algorithm is
  faster than previous algorithms when the largest weight is relatively sma
 ll.  Our approximation algorithm delivers a $(1-\\epsilon)$-approximate 
  solution with a running time significantly faster than most known exact a
 lgorithms.\n\nThe core of our algorithms is a decomposition technique: we 
 decompose an instance of the weighted matroid intersection problem into a 
 set of instances of the unweighted matroid intersection problem. The compu
 tational advantage of this approach is that we can make use of fast unweig
 hted matroid intersection algorithms as a black box for designing algorith
 ms. Precisely speaking\, we prove that we can solve the weighted matroid i
 ntersection problem via solving $W$ instances of the unweighted matroid in
 tersection problem\, where $W$ is the largest given weight. Furthermore\, 
 we can find a $(1-\\epsilon)$-approximate solution via solving $O(\\epsilo
 n^{-1} \\log r)$ instances of the unweighted matroid intersection problem\
 , where $r$ is the smallest rank of the given two matroids.\n\nBio: Chien-
 Chung Huang is currently an assistant professor at Chalmers University  o
 f Technology in Sweden. He obtained his Ph.D. at Dartmouth College in 2008
 \, under the supervision of Peter Winkler. He works in the area of algorit
 hm design  nd analysis. The major topics that he has worked on include st
 able matching\, machine scheduling\, and selfish routing games.\n
URL:https://www.tcs.tifr.res.in/web/events/664
DTSTART;TZID=Asia/Kolkata:20160315T160000
DTEND;TZID=Asia/Kolkata:20160315T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR
