25 citations · 36 across the 7 of their papers we have counts for
4 papers · 1 filter
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…