Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

DOI10.1007/b11961zbMath1279.05053OpenAlexW4298253479MaRDI QIDQ5900920

Kunal Talwar, Jittat Fakcharoenphol

Publication date: 26 May 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b11961

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83) Approximation algorithms (68W25)

Related Items (20)

Metric extension operators, vertex sparsifiers and Lipschitz extendability ⋮ Metric decompositions of path-separable graphs ⋮ Strong-diameter decompositions of minor free graphs ⋮ Unnamed Item ⋮ Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications ⋮ Metric uniformization and spectral bounds for graphs ⋮ Advances in metric embedding theory ⋮ Approximating Unique Games Using Low Diameter Graph Decomposition ⋮ On average distortion of embedding metrics into the line ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ Comparison of Metric Spectral Gaps ⋮ Space-efficient path-reporting approximate distance oracles ⋮ The intrinsic dimensionality of graphs ⋮ Multi-way spectral partitioning and higher-order cheeger inequalities ⋮ Extending Lipschitz functions via random metric partitions ⋮ Randomly removing \(g\) handles at once ⋮ Local embeddings of metric spaces ⋮ Multicommodity flows and cuts in polymatroidal networks ⋮ Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs ⋮ Conformal growth rates and spectral geometry on distributional limits of graphs

This page was built for publication: Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques