Directed metrics and directed graph partitioning problems

Moses Charikar*, Konstantin Makarychev, Yury Makarychev

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

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 languageEnglish (US)
Title of host publicationProceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Pages51-60
Number of pages10
DOIs
StatePublished - Feb 28 2006
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States
Duration: Jan 22 2006Jan 24 2006

Other

OtherSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityMiami, FL
Period1/22/061/24/06

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Directed metrics and directed graph partitioning problems'. Together they form a unique fingerprint.

Cite this