ARC Day with keynote by

Uriel Feige (Weizmann Institute)

Monday, February 8, 2021

Virtual via Bluejeans - 10:00 am

Title: Faithful rounding of linear programs

Abstract: A common paradigm in approximation algorithm is to formulate the NP-hard optimization problem as an integer program, relax it to a linear program, solve the linear program optimally, and then round the fractional solution to an integral solution. An instance of this approach that is relevant to the current talk is the algorithm of Lenstra, Shmoys and Tardos [1990] for scheduling unrelated parallel machines. The rounding technique developed there inspired more recent algorithms for allocation of indivisible items. The context of allocation problems involves fairness considerations that motivate a refined version of the rounding technique, that we refer to as ``faithful rounding". In this talk we shall explain the faithful rounding technique, survey some of its applications to allocation problems, and discuss challenges that remain in extracting more value out of this rounding technique. 

Bio:  Born in Jerusalem, Uriel Feige earned his BSc from the Technion, and his MSc and PhD from the Weizmann Institute of Science, both under the guidance of Adi Shamir. After conducting postdoctoral research at Princeton University and at the IBM T.J. Watson Research Center, he joined the Weizmann Institute in 1992. From 2004-2007, he took leave from the Weizmann Institute to work with Microsoft Research’s Theory Group, and he continues to serve as a visiting researcher in Microsoft Research, Herzeliya. His main research areas are algorithms, computational complexity, and algorithmic game theory. His work was recognized by some awards, including the 2001 Godel Prize and the 2005 SIAM Outstanding Paper Prize.

Uriel Feige's Webpage

_________________

Swati Gupta (Georgia Tech)

Title:  Electrical Flows over Spanning Trees

Abstract:  The network reconfiguration problem seeks to find a rooted tree T such that the energy of the (unique) feasible electrical flow over T is minimized. The tree requirement on the support of the flow is motivated by operational constraints in electricity distribution networks. Existing results on convex optimization over vertices of polytopes and on the structure of electrical flows do not give guarantees for this problem, while many heuristic methods have been developed in the power systems community as early as 1989. Our main contribution is to give the first provable approximation guarantees for the network reconfiguration problem. We provide novel lower bounds and corresponding approximation factors for various settings ranging from min{O(m − n), O(n)} for general graphs, to O(\sqrt{n}) over grids with uniform resistances on edges, and O(1) for grids with uniform edge resistances and demands. To obtain the result for general graphs, we propose a new method for (approximate) spectral graph sparsification, which may be of independent interest. Using insights from our theoretical results, we propose a general heuristic for the network reconfiguration problem that is orders of magnitude faster than existing methods in the literature, while obtaining comparable performance. This talk is based on joint work with Hassan Mortagy, Ali Khodabakhsh and Evdokia Nikolova.

Swati Gupta's Webpage

_________________

Anton Bernshteyn (Georgia Tech)

Title:  A fast distributed algorithm for $(\Delta + 1)$-edge-coloring

Abstract:  A celebrated theorem of Vizing says that every graph $G$ of maximum degree $\Delta$ is $(\Delta+1)$-edge-colorable. In this talk I will describe a deterministic distributed algorithm in the LOCAL model that finds a $(\Delta+1)$-edge-coloring in the number of rounds that is polynomial in $\Delta$ and $\log n$, where $n = |V(G)|$. This is the first distributed algorithm for $(\Delta + 1)$-edge-coloring with running time better than $O(\mathrm{diameter}(G))$.

Anton Bernshteyn's Webpage

_________________

Videos of recent talks are available at: http://arc.gatech.edu/node/121

Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu