Session Detail Information
Add this session to your itinerary

Cluster :  Optimization/ Network and Combinatorial Optimization

Session Information  : Sunday Nov 05, 10:00 - 11:30

Title:  Applications of the Arora-Rao-Vazirani Algorithm
Chair: Assaf Naor,Microsoft Research, One Microsoft Way, Redmond WA 98052-6399, United States, anaor@microsoft.com

Abstract Details

Title: Geometric Embeddings and Sparsest Cut Variants
 Presenting Author: James R. Lee,Professor, Institute for Advanced Study, 1 Einstein Drive, Princeton NJ 08540, United States, jrl@ias.edu
 
Abstract: In general, problems in the Sparsest Cut genre involve finding balanced separators in graphs: Our task is to break a given graph into two "large" pieces while minimizing the "interface" between them. Depending on the precise definition of these two objectives, different types of problems arise. We will discuss these variants and their applications, along with the known algorithmic results, and the relationship to semi-definite optimization and geometric embeddings.
  
Title: New Approximation Guarantee for Chromatic Number
 Presenting Author: Eden Chlamtac,Research Assistant, Princeton University, Computer Science Building, 35 Olden Street, Princeton NJ, United States, chlamtac@CS.Princeton.EDU
 Co-Author: Sanjeev Arora,Princeton University, 35 Olden St., Princeton NJ 08540, United States, arora@cs.princeton.edu
 Moses Charikar,Assistant Professor of Computer Science, Princeton University, 305 Computer Science Building, 35 Olden Street, Princeton NJ 08540, United States, moses@cs.princeton.edu
 
Abstract: We describe an algorithm which colors any 3-colorable graph using O(n^0.2074) colors, thus improving the algorithms of Karger, Motwani and Sudan, and Blum and Karger, which used O(n^3/14) colors. Using ideas inspired by the work of Arora, Rao and Vazirani, we demonstrate a better relation between vector chromatic number and true chromatic number. While this gives some improvement, we obtain our best result by adding "odd-cycle constraints" to the semidefinite program.
  
Title: Directed Metrics in Graph Optimization Problems
 Presenting Author: Yury Makarychev,Princeton University, 35 Olden Street, Princeton NJ 08540, United States, ymakaryc@cs.princeton.edu
 Co-Author: Amit Agarwal,Princeton University, 35 Olden Street, Princeton NJ 08540, United States, aagarwal@cs.princeton.edu
 Moses Charikar,Assistant Professor of Computer Science, Princeton University, 305 Computer Science Building, 35 Olden Street, Princeton NJ 08540, United States, moses@cs.princeton.edu
 Konstantin Makarychev,Princeton University, 35 Olden Street, Princeton NJ 08540, United States, kmakaryc@cs.princeton.edu
 
Abstract: The theory of metric embeddings has provided a powerful toolkit for undirected graph partitioning problems. The metrics of interest arise naturally as solutions of mathematical programming relaxations for graph partitioning problems. No analog of this embedding theory exists for directed (asymmetric) metrics, the natural distance functions that arise in considering directed problems. We discuss some successes and some obstacles in extending the embedding machinery to directed metrics.
  
Title: A New Integrality Gap for the Semidefinite Relaxation of Sparsest Cut
 Presenting Author: Assaf Naor,Microsoft Research, One Microsoft Way, Redmond WA 98052-6399, United States, anaor@microsoft.com
 
Abstract: In this talk I will show that the Heisenberg group has an equivalent metric which is in squared L_2, yet it does not embed into L_1. It follows that the classical Heisenberg geometry on R^3 is a simple counter example to the Goemans-Linial conjecture on the integrality gap of the semidefinite relaxation of the Sparsest Cut Problem. Based on joint work with James R. Lee