Search results for "sparsest cut"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Shuchi Chawla, Anupam Gupta, Harald Räcke	Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut.	ACM Transactions on Algorithms	2008	DBLP DOI BibTeX RDF	negative-type metric, Approximation algorithm, metrics, embedding, sparsest cut
3	Sanjeev Arora, James R. Lee, Assaf Naor	Euclidean distortion and the sparsest cut.	STOC	2005	DBLP DOI BibTeX RDF	approximation algorithms, semidefinite programming, metric embeddings, sparsest cut
2	Jeff Cheeger, Bruce Kleiner, Assaf Naor	A (log n)Omega(1) Integrality Gap for the Sparsest Cut SDP.	FOCS	2009	DBLP DOI BibTeX RDF	Sparsest Cut problem, Heisenberg group, semidefinite programming, metric embeddings, integrality gap
2	Julia Chuzhoy, Sanjeev Khanna	Polynomial flow-cut gaps and hardness of directed cut problems.	J. ACM	2009	DBLP DOI BibTeX RDF	Directed multicut, hardness of approximation, sparsest cut
2	Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani, Nisheeth K. Vishnoi	On partitioning graphs via single commodity flows.	STOC	2008	DBLP DOI BibTeX RDF	edge-separator, single-commodity max-flow, graph partitioning, spectral method, sparsest cut, matrix exponential
2	Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson	Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling.	FOCS	2007	DBLP DOI BibTeX RDF
2	Amit Agarwal, Noga Alon, Moses Charikar	Improved approximation for directed cut problems.	STOC	2007	DBLP DOI BibTeX RDF	directed multicut, directed sparsest cut, approximation algorithm, linear programming relaxation
2	Sanjeev Arora, Satyen Kale	A combinatorial, primal-dual approach to semidefinite programs.	STOC	2007	DBLP DOI BibTeX RDF	balanced separator, matrix multiplicative weights, min UnCut, semidefinite programming, sparsest cut
2	Julia Chuzhoy, Sanjeev Khanna	Polynomial flow-cut gaps and hardness of directed cut problems.	STOC	2007	DBLP DOI BibTeX RDF	concurrent flow, directed multicut, directed sparsest cut, flow-cut gaps, hardness of approximation, multicommodity flow
2	Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar	On the Hardness of Approximating Multicut and Sparsest-Cut.	Computational Complexity	2006	DBLP DOI BibTeX RDF	68Q17, Subject classification
2	Nikhil R. Devanur, Subhash Khot, Rishi Saket, Nisheeth K. Vishnoi	Integrality gaps for sparsest cut and minimum linear arrangement problems.	STOC	2006	DBLP DOI BibTeX RDF
2	Julia Chuzhoy, Sanjeev Khanna	Hardness of cut problems in directed graphs.	STOC	2006	DBLP DOI BibTeX RDF	directed multicut, hardness of approximation, sparsest cut
2	Shuchi Chawla, Anupam Gupta, Harald Räcke	Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut.	SODA	2005	DBLP DOI BibTeX RDF
2	Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar	On the Hardness of Approximating Multicut and Sparsest-Cut.	IEEE Conference on Computational Complexity	2005	DBLP DOI BibTeX RDF
2	Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev	O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems.	STOC	2005	DBLP DOI BibTeX RDF	directed balanced separator, directed sparsest cut, min 2CNF deletion, min UnCut, min multicut
2	Sanjeev Arora, Elad Hazan, Satyen Kale	0(sqrt (log n)) Approximation to SPARSEST CUT in Õ(n2) Time.	FOCS	2004	DBLP DOI BibTeX RDF
2	Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair	Cuts, Trees and l1-Embeddings of Graphs.	FOCS	1999	DBLP DOI BibTeX RDF	embeddings, Multicommodity flow, Sparsest cut, Finite metric spaces
1	Luis A. A. Meira, Flávio Keidi Miyazawa	Semidefinite Programming Based Algorithms for the Sparsest Cut Problem.	RAIRO - Operations Research	2011	DBLP DOI BibTeX RDF
1	Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson	Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut.	SIAM J. Comput.	2011	DBLP DOI BibTeX RDF
1	Éric Gourdin	A Mixed Integer Model for the Sparsest Cut problem.	Electronic Notes in Discrete Mathematics	2010	DBLP DOI BibTeX RDF
1	Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra	Approximating Sparsest Cut in Graphs of Bounded Treewidth	CoRR	2010	DBLP BibTeX RDF
1	Sanjeev Arora, Elad Hazan, Satyen Kale	O(sqrt(log(n)) Approximation to SPARSEST CUT in Õ(n2) Time.	SIAM J. Comput.	2010	DBLP DOI BibTeX RDF
1	Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra	Approximating Sparsest Cut in Graphs of Bounded Treewidth.	APPROX-RANDOM	2010	DBLP DOI BibTeX RDF
1	Jeff Cheeger, Bruce Kleiner, Assaf Naor	A $(\log n)^{\Omega(1)}$ integrality gap for the Sparsest Cut SDP	CoRR	2009	DBLP BibTeX RDF
1	Jonah Sherman	Breaking the Multicommodity Flow Barrier for sqrt(log(n))-Approximations to Sparsest Cut	CoRR	2009	DBLP BibTeX RDF
1	Maria-Florina Balcan	Better Guarantees for Sparsest Cut Clustering.	COLT	2009	DBLP BibTeX RDF
1	Jonah Sherman	Breaking the Multicommodity Flow Barrier for O(vlog n)-Approximations to Sparsest Cut.	FOCS	2009	DBLP DOI BibTeX RDF
1	John Dunagan, Alice X. Zheng, Daniel R. Simon	Heat-ray: combating identity snowball attacks using machinelearning, combinatorial optimization and attack graphs.	SOSP	2009	DBLP DOI BibTeX RDF	identity snowball, machine learning, support vector machine, authentication, access control, combinatorial optimization, attack graph, sparsest cut
1	Moses Charikar, Konstantin Makarychev, Yury Makarychev	Integrality gaps for Sherali-Adams relaxations.	STOC	2009	DBLP DOI BibTeX RDF	Sherali-Adams hierarchy, lift-and-project methods, local-global metric spaces
1	James R. Lee, Anastasios Sidiropoulos	On the geometry of graphs with a forbidden minor.	STOC	2009	DBLP DOI BibTeX RDF	forbidden minors, geometry of graphs, embeddings
1	Sanjeev Arora, Satish Rao, Umesh V. Vazirani	Expander flows, geometric embeddings and graph partitioning.	J. ACM	2009	DBLP DOI BibTeX RDF	Graph partitioning, semidefinite programs, multicommodity flows, expanders, expansion, graph separators
1	Rohit Khandekar, Satish Rao, Umesh V. Vazirani	Graph partitioning using single commodity flows.	J. ACM	2009	DBLP DOI BibTeX RDF	Edge-separator, single commodity max-flow, sparse cut, spectral method
1	Shuchi Chawla	Sparsest Cut.	Encyclopedia of Algorithms	2008	DBLP DOI BibTeX RDF
1	Zoya Svitkina, Lisa Fleischer	Submodular Approximation: Sampling-based Algorithms and Lower Bounds.	FOCS	2008	DBLP DOI BibTeX RDF
1	Chandra Chekuri, Sanjeev Khanna	Algorithms for 2-Route Cut Problems.	ICALP	2008	DBLP DOI BibTeX RDF
1	Sanjeev Arora, James R. Lee, Assaf Naor	Fréchet Embeddings of Negative Type Metrics.	Discrete & Computational Geometry	2007	DBLP DOI BibTeX RDF	Sparsest cut problem, Euclidean, L 1, Distortion, Metric embeddings
1	Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis	Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy.	FOCS	2007	DBLP DOI BibTeX RDF
1	Mohammad Taghi Hajiaghayi, Harald Räcke	An O(sqrt(n))-approximation algorithm for directed sparsest cut.	Inf. Process. Lett.	2006	DBLP DOI BibTeX RDF
1	Moses Charikar, Konstantin Makarychev, Yury Makarychev	Directed metrics and directed graph partitioning problems.	SODA	2006	DBLP DOI BibTeX RDF
1	Robert Krauthgamer, Yuval Rabani	Improved lower bounds for embeddings into L1.	SODA	2006	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Eden Chlamtac	New approximation guarantee for chromatic number.	STOC	2006	DBLP DOI BibTeX RDF	approximation algorithms, graph coloring, semidefinite programming, chromatic number
1	Rohit Khandekar, Satish Rao, Umesh V. Vazirani	Graph partitioning using single commodity flows.	STOC	2006	DBLP DOI BibTeX RDF	edge-separator, single commodity max-flow, sparse cut, spectral method
1	Iannis Tourlakis	New Lower Bounds for Vertex Cover in the Lovasz-Schrijver Hierarchy.	IEEE Conference on Computational Complexity	2006	DBLP DOI BibTeX RDF
1	James R. Lee, Assaf Naor	Lp metrics on the Heisenberg group and the Goemans-Linial conjecture.	FOCS	2006	DBLP DOI BibTeX RDF
1	Roee Engelberg, Jochen Könemann, Stefano Leonardi, Joseph Naor	Cut Problems in Graphs with a Budget Constraint.	LATIN	2006	DBLP DOI BibTeX RDF
1	James R. Lee	On distance scales, embeddings, and efficient relaxations of the cut cone.	SODA	2005	DBLP DOI BibTeX RDF
1	Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis	Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy.	STOC	2005	DBLP DOI BibTeX RDF	Lovász-Schrijver matrix cuts, inapproximability, integrality gaps
1	Subhash Khot	Guest column: inapproximability results via Long Code based PCPs.	SIGACT News	2005	DBLP DOI BibTeX RDF
1	Subhash Khot	On the Unique Games Conjecture.	FOCS	2005	DBLP DOI BibTeX RDF
1	Subhash Khot, Nisheeth K. Vishnoi	The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l1.	FOCS	2005	DBLP DOI BibTeX RDF
1	Iannis Tourlakis	Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
1	George Karakostas	A Better Approximation Ratio for the Vertex Cover Problem.	ICALP	2005	DBLP DOI BibTeX RDF
1	Sanjeev Arora, Satish Rao, Umesh V. Vazirani	Expander flows, geometric embeddings and graph partitioning.	STOC	2004	DBLP DOI BibTeX RDF
1	James R. Lee, Manor Mendel, Assaf Naor	Metric Structures in L1: Dimension, Snowflakes, and Average Distortion.	LATIN	2004	DBLP DOI BibTeX RDF
1	Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair	Cuts, Trees and l1-Embeddings of Graphs.	Combinatorica	2004	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C12, 90C27, 68R10, 05C85
1	Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair	Embedding k-outerplanar graphs into l1.	SODA	2003	DBLP DOI BibTeX RDF