BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/725
DTSTAMP:20230914T125935Z
SUMMARY:Randomized Rounding Revisited
DESCRIPTION:Speaker: Sandeep Sen (Indian Institute of Technology\nDepartmen
 t of Computer Science\nand Engineering\nHauz Khas\nNew Delhi 110016)\n\nAb
 stract: \nWe develop new techniques for rounding packing integer programs 
 using iterative randomized rounding. It is based on a novel application of
  multidimensional Brownian motion in $\\mathbb{R}^n$. Let $\\overset{\\sim
 }{x} \\in {[0\,1]}^n$ be a fractional feasible solution of a packing const
 raint $A x \\leq 1\,\\ \\ $ $A \\in {\\{0\,1 \\}}^{m\\times n}$ that maxim
 izes a linear objective function.\n\nOur algorithm iteratively transforms 
 $\\overset{\\sim}{x}$ to $\\hat{x} \\in {\\{ 0\,1\\}}^{n}$ using a random 
 walk\, such that the expected values of $\\hat{x}_i$'s are consistent with
  the Raghavan-Thompson rounding. In addition\, it gives us intermediate va
 lues $x'$ which can then be used to bias the rounding towards a superior s
 olution.  Our algorithm  gradually sparsifies $A$ to $A' \\in {\\{0\,1 \
 \}}^{m\\times n}$ where each row in $A'$ has $\\leq \\log n$ non-zero coef
 ficients with $A'\\cdot x' \\leq O(1)$. The reduced dependencies between t
 he constraints of the sparser system can be exploited using {\\it Lovasz L
 ocal Lemma}. Using the Moser-Tardos' constructive version\, $x'$ converges
  to $\\hat{x}$ in polynomial time to a distribution over the unit hypercub
 e ${\\cal H}_n = {\\{0\,1 \\}}^n$ such that the expected value of any line
 ar objective function over ${\\cal H}_n$ equals the value at $\\overset{\\
 sim}{x}$.\n\nWe discuss application of these techniques when $A$ is a rand
 om matrix and also for a more general situation of a  $k$-column sparse m
 atrix (joint work with Dhiraj Madan).\n
URL:https://www.tcs.tifr.res.in/web/events/725
DTSTART;TZID=Asia/Kolkata:20161122T160000
DTEND;TZID=Asia/Kolkata:20161122T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR