BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of California\, Berkeley//UCB Events Calendar//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/Los_Angeles
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
DTSTART:19701029T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:19700402T020000
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20170427T060014Z
DTSTART;TZID=America/Los_Angeles:20170504T140000
DTEND;TZID=America/Los_Angeles:20170504T150000
TRANSP:OPAQUE
SUMMARY:Dissertation Talk: Fast Approximation Algorithms for Positive Linear Programs
UID:108949-ucb-events-calendar@berkeley.edu
ORGANIZER;CN="UC Berkeley Calendar Network":
LOCATION:380 Soda Hall
DESCRIPTION:Di Wang\n\nPositive linear programs (LPs) are LPs formulated with non-negative coefficients\, non-negative constraints and non-negative variables. This class of LPs models a wide range of fundamental problems in combinatorial optimization and operations research\, thus have long drawn interest in theoretical computer science. Notable special cases include packing LPs and covering LPs\, which apply to most resource allocation problems. \n\nAlthough one can use general LP solvers such as interior-point method to solve positive LPs with high precision\, i.e. $\\log(1/\\epsilon)$ convergence for $\\epsilon$-approximate solution\, such algorithms usually have very high computation cost\, as operations such as the computation of the Hessian and matrix inversion are involved. With the abundance of large-scale data-sets\, fast low precision iterative solvers are of great interest. Such solvers compute approximate solutions usually in time (or total work for parallel solvers) with nearly linear dependence\non the problem size\, and $poly(1/\\epsilon)$ dependence on the approximation parameter $\\epsilon$.\n\nWe study iterative solvers with faster convergence for positive LPs\, and achieve improved algorithms\, both sequential and parallel\, for positive LPs\, as well as the special cases of packing LPs and covering LPs. In particular\, we design various algebraic and combinatorial techniques\, and organically integrate them in the algorithms.
URL:http://events.berkeley.edu/index.php/calendar/sn/pubaff.html?event_ID=108949&view=preview
SEQUENCE:0
CLASS:PUBLIC
CREATED:20170427T060014Z
LAST-MODIFIED:20170427T154819Z
X-MICROSOFT-CDO-BUSYSTATUS:BUSY
X-MICROSOFT-CDO-INSTTYPE:0
X-MICROSOFT-CDO-IMPORTANCE:1
X-MICROSOFT-CDO-OWNERAPPTID:-1
END:VEVENT
END:VCALENDAR