25 citations · 36 across the 7 of their papers we have counts for
8 papers
Symmetric Linear Programming Formulations for Minimum Cut with Applications to TSP
Robert D. Carr, Jennifer Iglesias, Giuseppe Lanciac +1
We introduce multiple symmetric LP relaxations for minimum cut problems. The relaxations give optimal and approximate solutions when the input is a Hamiltonian cycle. We show that…
Coloring Down: -approximation for special cases of the weighted tree augmentation problem
Jennifer Iglesias, R. Ravi
In this paper, we investigate the weighted tree augmentation problem (TAP), where the goal is to augment a tree with a minimum cost set of edges such that the graph becomes two edg…
Single-sink Fractionally Subadditive Network Design
Guru Guruganesh, Jennifer Iglesias, R. Ravi +1
We study a generalization of the Steiner tree problem, where we are given a weighted network together with a collection of subsets of its vertices and a root . We wish t…
Plane Gossip: Approximating rumor spread in planar graphs
Jennifer Iglesias, Rajmohan Rajaraman, R Ravi +1
We study the design of schedules for multi-commodity multicast; we are given an undirected graph and a collection of source destination pairs, and the goal is to schedule a min…
Balls and Funnels: Energy Efficient Group-to-Group Anycasts
Jennifer Iglesias, Rajmohan Rajaraman, R. Ravi +1
We introduce group-to-group anycast (g2g-anycast), a network design problem of substantial practical importance and considerable generality. Given a collection of groups and requir…
Egalitarian Graph Orientations
Glencora Borradaile, Jennifer Iglesias, Theresa Migler +3
Given an undirected graph, one can assign directions to each of the edges of the graph, thus orienting the graph. To be as egalitarian as possible, one may wish to find an orientat…
Computing with voting trees
Jennifer Iglesias, Nathaniel Ince, Po-Shen Loh
The classical paradox of social choice theory asserts that there is no fair way to deterministically select a winner in an election among more than two candidates; the only definit…
Length 3 Edge-Disjoint Paths and Partial Orientation
Hannah Alpert, Jennifer Iglesias
In 2003, it was claimed that the following problem was solvable in polynomial time: do there exist k edge-disjoint paths of length exactly 3 between vertices s and t in a given gra…