## Abstract

The theory of embeddings of finite metrics has provided a powerful toolkit for graph partitioning problems in undirected graphs. The connection comes from the fact that the integrality gaps of mathematical programming relaxations for sparsest cut in undirected graphs is exactly equal to the minimum distortion required to embed certain metrics into ℓ _{1}. No analog of this metric embedding theory exists for directed (asymmetric) metrics, the natural distance functions that arise in considering mathematical relaxations for directed graph partioning problems. We initiate a study of metric embeddings for directed metrics, motivated by understanding directed variants of sparsest cut. It turns out that there are two different ways to formulate sparsest cut in directed graphs (depending on whether one insists on partitioning the graph into two pieces or not). Different subclasses of directed metrics arise in the consideration of mathematical relaxations for these two formulations and the embedding questions that result are quite different. Unlike in the undirected case, where the natural host space is ℓ _{1}, the host space in the directed case is not obvious and depends on the problem formulation. Our work is a first step at understanding this space of directed metrics, the resulting embedding questions and their relationships to directed graph partitioning problems.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms |

Pages | 51-60 |

Number of pages | 10 |

DOIs | |

State | Published - Feb 28 2006 |

Event | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States Duration: Jan 22 2006 → Jan 24 2006 |

### Other

Other | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country/Territory | United States |

City | Miami, FL |

Period | 1/22/06 → 1/24/06 |

## ASJC Scopus subject areas

- Software
- General Mathematics