Bypassing the embedding
From MaRDI portal
Publication:3580975
DOI10.1145/1007352.1007399zbMATH Open1192.68918OpenAlexW2053578961MaRDI QIDQ3580975FDOQ3580975
Authors: Kunal Talwar 
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
Recommendations
- Approximation algorithms for low-distortion embeddings into low-dimensional spaces
- Approximation algorithms for low-distortion embeddings into low-dimensional spaces
- Ultra-low-dimensional embeddings for doubling metrics
- Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
- On low dimensional local embeddings
- Computing the nearest Euclidean distance matrix with low embedding dimensions
- Low distortion metric embedding into constant dimension
- Metric embeddings -- beyond one-dimensional distortion
Cited In (68)
- Localized and compact data-structure for comparability graphs
- Low-Distortion Inference of Latent Similarities from a Multiplex Social Network
- Pattern matching in doubling spaces
- Geodesic spanners for points in \(\mathbb{R}^3\) amid axis-parallel boxes
- Hierarchical routing over dynamic wireless networks
- A Modern View on Stability of Approximation
- Polynomial time approximation schemes for clustering in low highway dimension graphs
- Small hop-diameter sparse spanners for doubling metrics
- Dynamic Routing and Location Services in Metrics of Low Doubling Dimension
- Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
- Title not available (Why is that?)
- On Hop-Constrained Steiner Trees in Tree-Like Metrics
- Estimating the embedding dimension
- Geometric spanners for weighted point sets
- Generalized \(k\)-center: distinguishing doubling and highway dimension
- Linear-size universal discretization of geometric center-based problems in fixed dimensions
- Vertex Fault-Tolerant Geometric Spanners for Weighted Points
- Using the doubling dimension to analyze the generalization of learning algorithms
- Computing the greedy spanner in near-quadratic time
- Load balanced distributed directories
- Shifting strategy for geometric graphs without geometry
- Ramsey partitions and proximity data structures
- Title not available (Why is that?)
- Fractal dimension and lower bounds for geometric problems
- On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$
- Title not available (Why is that?)
- A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- Distributed transactional memory for general networks
- Geodesic Spanners for Points on a Polyhedral Terrain
- Additive spanners and distance and routing labeling schemes for hyperbolic graphs
- Efficient approximation of the metric CVRP in spaces of fixed doubling dimension
- Boolean percolation on doubling graphs
- Distributed transactional memory for metric-space networks
- Distance Labeling for Permutation Graphs
- Distance and routing labeling schemes for cube-free median graphs
- Near isometric terminal embeddings for doubling metrics
- Making doubling metrics geodesic
- Approximation algorithms for low-distortion embeddings into low-dimensional spaces
- Non-uniform packings
- Metric decompositions of path-separable graphs
- Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension
- Title not available (Why is that?)
- Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension
- The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
- Ultra-low-dimensional embeddings for doubling metrics
- Distance estimation and object location via rings of neighbors
- Approximation schemes for node-weighted geometric Steiner tree problems
- A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
- A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
- Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median
- Local Search Yields a PTAS for $k$-Means in Doubling Metrics
- The black-box complexity of nearest-neighbor search
- Light spanners for high dimensional norms via stochastic decompositions
- Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
- Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension
- Spanners for geodesic graphs and visibility graphs
- A PTAS for the Steiner Forest Problem in Doubling Metrics
- Near Isometric Terminal Embeddings for Doubling Metrics
- Vertex fault-tolerant spanners for weighted points in polygonal domains
- A data-dependent approach for high-dimensional (robust) Wasserstein alignment
- A PTAS framework for clustering problems in doubling metrics
- Routing on heavy path WSPD spanners
- Approximation algorithms for fair \(k\)-median problem without fairness violation
- Travelling on graphs with small highway dimension
- Title not available (Why is that?)
- Approximation schemes for Min-Sum \(k\)-Clustering
- Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction
- Title not available (Why is that?)
This page was built for publication: Bypassing the embedding
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3580975)
