News Archives

[Colloquium] We explore a new edge-connectivity problem

March 4, 2015

Watch Colloquium: 

MOV FILE

  • Date: Tuesday, 3/3/15
  • Time: 11:00 AM - 12:15 PM
  • Place: Mechanical Engineering, Room 218

Speaker: Robert D. Carr, Sandia National Laboratories 

Title: We explore a new edge-connectivity problem. That is, find a minimum cost 2-edge connected spanning subgraph where there is a discount for selecting a doubled multi-edge. We show this is closely related to the traveling salesman problem. We give a factor 5/3 approximation for this new edge-connectivity problem.

Short bio:
Robert D. Carr is a discrete mathematician/computer scientist specializing in integer programming and polyhedral combinatorics, formal (proof) methods, and quantum computing. Research interests include integrality gaps for integer programs, compact linear programming formulations, an interest in structuring proofs in mathematics, quantum error correction, and adiabatic quantum computing. He got both a bachelors in physics/math and a PhD in mathematics from Carnegie Mellon University, graduating in 1995. After having postdocs at the University of Ottawa and Carnegie Mellon, Bob became a research staff member for Sandia National Laboratories in the fall of 1997, becoming a senior staff member in the spring of 2000. In the spring of 2001, he became adjunct faculty in computer science at the University of New Mexico and taught a graduate course in polyhedral combinatorics. He contributed a chapter with Professor Goran Konjevod at Lawrence Livermore National Laboratories on polyhedral combinatorics to the INFORM?s book on Emerging Technologies in Optimization, which was presented at INFORMS in the Fall of 2004. Perhaps the paper he is proudest of is the paper ?Compacting cuts: a new linear programming formulation for minimum cut? with Konjevod,Little,Natarajan, and Parekh, in ACM Transactions on Algorithms 2009 in an issue of invited papers from SODA 2007 (Symposium on Discrete Algorithms).