Bypassing the embedding
From MaRDI portal
Publication:3580975
DOI10.1145/1007352.1007399zbMath1192.68918OpenAlexW2053578961MaRDI QIDQ3580975
Publication date: 15 August 2010
Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1007352.1007399
Related Items (60)
Linear-size universal discretization of geometric center-based problems in fixed dimensions ⋮ Pattern matching in doubling spaces ⋮ Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median ⋮ A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ Load balanced distributed directories ⋮ Hierarchical routing over dynamic wireless networks ⋮ Approximation schemes for node-weighted geometric Steiner tree problems ⋮ Near isometric terminal embeddings for doubling metrics ⋮ Metric decompositions of path-separable graphs ⋮ Generalized \(k\)-center: distinguishing doubling and highway dimension ⋮ Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension ⋮ Making doubling metrics geodesic ⋮ A Modern View on Stability of Approximation ⋮ Unnamed Item ⋮ Vertex Fault-Tolerant Geometric Spanners for Weighted Points ⋮ Additive spanners and distance and routing labeling schemes for hyperbolic graphs ⋮ Approximation algorithms for fair \(k\)-median problem without fairness violation ⋮ Geometric spanners for weighted point sets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Spanners for geodesic graphs and visibility graphs ⋮ Distance estimation and object location via rings of neighbors ⋮ Distributed transactional memory for metric-space networks ⋮ Computing the greedy spanner in near-quadratic time ⋮ A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs ⋮ A PTAS for the Steiner Forest Problem in Doubling Metrics ⋮ Shifting strategy for geometric graphs without geometry ⋮ Unnamed Item ⋮ A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics ⋮ Using the doubling dimension to analyze the generalization of learning algorithms ⋮ Dynamic Routing and Location Services in Metrics of Low Doubling Dimension ⋮ Distance and routing labeling schemes for cube-free median graphs ⋮ Geodesic spanners for points in \(\mathbb{R}^3\) amid axis-parallel boxes ⋮ Polynomial time approximation schemes for clustering in low highway dimension graphs ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median ⋮ Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs ⋮ Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension ⋮ Small hop-diameter sparse spanners for doubling metrics ⋮ Distributed transactional memory for general networks ⋮ Geodesic Spanners for Points on a Polyhedral Terrain ⋮ Ramsey partitions and proximity data structures ⋮ Vertex fault-tolerant spanners for weighted points in polygonal domains ⋮ Fractal dimension and lower bounds for geometric problems ⋮ Efficient approximation of the metric CVRP in spaces of fixed doubling dimension ⋮ Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction ⋮ Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension ⋮ Unnamed Item ⋮ Boolean percolation on doubling graphs ⋮ The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme ⋮ Travelling on graphs with small highway dimension ⋮ Non-uniform packings ⋮ Localized and compact data-structure for comparability graphs ⋮ On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$ ⋮ Near Isometric Terminal Embeddings for Doubling Metrics ⋮ Light spanners for high dimensional norms via stochastic decompositions ⋮ Low-Distortion Inference of Latent Similarities from a Multiplex Social Network ⋮ The black-box complexity of nearest-neighbor search ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics ⋮ Distance Labeling for Permutation Graphs
This page was built for publication: Bypassing the embedding
