To join this virtual meeting via Zoom, click here.
This Zoom meeting requires a passcode. Email the organizers (Cameron Musco or Rik Sengupta) if you need the Zoom password, or see emails on the seminars list.
Title: Algorithms for constructing separating set systems over graphs
Abstract: Given a graph G(V, E), a separating set system is a collection of sets S_1, S_2, .. such that for every edge e in E, there exists a set S_i contains exactly one end point of e. Our goal is to construct "good" separating set systems for any given graph G. Separating set systems have many applications, and more recently they have been used to discover the directions of edges of a causal graph. In this talk, we will consider a cost model where every node in V has an associated cost, and the cost of constructing a set S_i is equal to the sum of the costs of all the nodes in Si. First, we will see that, conditioned on the hardness of approximate graph coloring, no polynomial time algorithm can achieve an approximation factor better than \Theta(\log n), where n is the number of nodes in G. We also give simple algorithms that achieve this factor. Then, we relax the goal and introduce a bi-criteria approximation goal that lets us "separate" all but \epsilon n^2 edges in G, for some specified error parameter epsilon > 0. Under this relaxed goal, we provide a construction that achieves a cost within a small constant factor of the optimal.