Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [metric-spaces]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
70 views

Does the Christofides algorithm ensure this inequality?

Let $(X,d)$ be a finite metric space. Let $C$ be a Hamiltonian cycle (over $X$) outputted by Christofide's algorithm. Also, let $K$ be a minimum spanning tree. I am aware that Christofide's algorithm ...
advocateofnone's user avatar
6 votes
0 answers
246 views

Does k-Median problem become any easier when L = C?

In the $k$-median problem, $L$ defines as set of feasible facility locations and $C$ defines a set of client locations in a metric space. The current best approximation guarantee for the problem is $2....
Inuyasha Yagami's user avatar
3 votes
0 answers
135 views

Dimentionality Reduction for Lp-Normed Spaces

Are there any dimensionality reduction techniques known for the general $\ell_{p}$-normed spaces for $p \geq 1$? In the Euclidean space, there is a classical result: Johnson-Lindenstrass lemma that ...
Inuyasha Yagami's user avatar
5 votes
2 answers
250 views

kmeans++ for arbitrary metric spaces and general potential function

I was reading this popular paper "k-means++: The Advantages of Careful Seeding". It appeared in SODA 2007. Since this technique is the most popular clustering technique, I am hoping that my question ...
Inuyasha Yagami's user avatar
4 votes
1 answer
161 views

Citation for isometric embeddability of $\ell_2$ into $\ell_p^\binom{n}{2}$ for $p \geq 1$?

I need to use the following well-known result in my paper: Let $X$ be a set of $n$ points in $\mathbb{R}^d$. Then $(X,\ell_2^d)$ embeds isometrically in $\ell_p^\binom{n}{2}$ for all $p \geq 1$. ...
Elliot Gorokhovsky's user avatar
1 vote
1 answer
173 views

Finding the size $k$ subset in a metric space that maximizes the min distance between elements

I have a metric space $(X,d)$ and I'd like to find a subset of size k of far away elements. We can cast this as the following optimization problem $\max_{S \subseteq X, |S| = k} ( \min_{i \not = j, ...
Elle Najt's user avatar
  • 1,469
3 votes
0 answers
80 views

Embed graph in $\ell_2$ space so that edge and non-edge distances are separated by a constant factor

Suppose I have an undirected unweighted graph $G = (V,E)$. Is there a way to compute points $x_v \in \mathbb{R}^d$ for each vertex $v \in V$ such that $||x_v - x_u|| = 1$ whenever $(u,v) \in E$ and $ |...
Elliot Gorokhovsky's user avatar
1 vote
0 answers
80 views

Points of a finite set wihtin a ball

I am looking for data-structures to store efficiently a set of points $E$ in an euclidean space of dimension $d$. In particular, I would like to be able to solve the problem of finding all the point ...
C.P.'s user avatar
  • 992
4 votes
0 answers
132 views

Do features always induce a metric?

It is well-known in functional analysis that an inner product always induces a norm and a norm always induces a metric, and the reverse directions do not hold in general. I am wondering if a similar ...
Aryeh's user avatar
  • 10.6k
1 vote
0 answers
41 views

BK-Tree intersection

I'm looking to calculate the approximate intersection (proximity under a certain distance) of two sets of points in a discrete metric space. In other words, given a metric space $(M, d)$, subsets $A, ...
Vladimir Panteleev's user avatar
1 vote
1 answer
116 views

Subclasses or characterizations of modular or pseudo-modular planar graphs

We say that a graph G is modular if for every three vertices x,y,z there exists a vertex w that lies on a shortest path between every two of x, y, z. Pseudo-modular (or "3-Helly") graphs are defined ...
aellab's user avatar
  • 429
0 votes
1 answer
209 views

A metric space on Turing machines

Let $L$ be a decidable language. Let $X^L$ be the set of deterministic Turing machines which decide $L$. Define two machines $A,B\in X^L$ to be time-equivalent if $t_A(w) = t_B(w)$ for all $w \in \...
user avatar
3 votes
0 answers
107 views

Embedding distortion under group quotient

The high level question is as follows: Suppose some group (here assumed to be a vector space of $\mathbf{F}_2^n$) has a low-distortion embedding into $l_1$. Under what condition does the quotient of ...
Lior Eldar's user avatar
  • 1,224
4 votes
2 answers
219 views

Are there Similar Distance Binary Error Correcting Codes?

I'm trying to find a low distortion embedding of the trivial metric space into hamming space. It seems this should be doable by using a large set of low dimensional vectors, with approximately equal ...
Thomas Ahle's user avatar
11 votes
1 answer
250 views

Compute lowest dimensional polytope from a given set of sign vectors

Given a set of hyperplanes determined by the normal vectors $h_1,\dots,h_m \in \mathbf R^d$, its cell types (or sign vectors) are all vectors $t\in\{+,-\}^m$ for which there exists a vector $v\in\...
Holger's user avatar
  • 975
3 votes
0 answers
136 views

Approximation of covering number in metric space

Consider the following setting: Let $(X,d)$ be a metric space and let $S$ be a finite subset of $X$. An $\epsilon$-cover of $S$ is any subset $C\subset S$ such that $$ \max_{x\in S} d(x,C)\leq \...
sirolf's user avatar
  • 201
5 votes
2 answers
207 views

L1 - embeddability of metrics supported on the Hypercube

I am quite new to the area of metric embeddings so this question might turn out to be extremely easy. Consider a metric supported on the edges of a boolean hypercube. By supported I mean every edge ...
NAg's user avatar
  • 666
1 vote
0 answers
90 views

Are there any polynomial cases of Balanced Minimum Evolution?

The BME problem has an interest in computational biology, for the reconstruction of phylogenetic trees from a distance matrix. Let me provide some context before defining the problem. Suppose that we ...
Super8's user avatar
  • 324
0 votes
1 answer
92 views

Define metric for systems of set of points

Given a set of points $p_1, p_2, ..., p_n$ and a collection of sets from $n$ points $S_1, S_2,...,S_m$. The pairwise distance between any three points $(p_1, p_2, p_3)$ satisfies triangle inequality $...
Hung Le's user avatar
  • 305
3 votes
0 answers
127 views

Fixed orientation metrics

I am currently working on some computational geometry problems with non-euclidean metrics, and have some trouble on a fact that sounds easy enough, at least intuitively. The fact is as follows: Given ...
user19549's user avatar
2 votes
0 answers
154 views

Quality measure for clusters of a metric space embedding of a graph?

When evaluating clustering algorithms for networks, we have well-established metrics like Modularity and Surprise for evaluating the quality of the resulting partition. If we then embed our graph (...
donnyton's user avatar
  • 161
3 votes
1 answer
3k views

Non-metric distances

Could anybody suggest practically important distances that are significantly non-metric and are not Bregman divergences? For instance, they are non-symmetric and not equivalent to the Euclidean ...
Leonid Boytsov's user avatar
2 votes
1 answer
389 views

An intuitive justification - Metric Embedding Based Approximation Algorithms

Recently, I started (independent) learning of the theory of metric embeddings from the Fall 2003 course offered at CMU . I had a very basic question from the very first lecture of this course ...
Akash Kumar's user avatar
  • 1,973
1 vote
1 answer
72 views

Term for a correspondence of two point sets regarding their ordering in each dimension

Let there be two sets of points $S$ and $S'$ in $R^d$. $|S| = |S'|$, and for each point $s_i$ in $S$ it exists exactly one corresponding point $s'_i$ in $S'$, such that the ordering of ...
0__'s user avatar
  • 173
7 votes
1 answer
261 views

Has anyone studied "polynomially compact" metric spaces?

A subspace $S$ of a metric space $A$ is compact if it is complete and totally bounded. Here, complete means that every Cauchy sequence in $S$ has a limit also in $S$. For $S$ to be totally bounded, ...
Neel Krishnaswami's user avatar
4 votes
1 answer
183 views

Need a term for a graph-theoretic/metric concept

Let $(X,d)$ be a metric space, and define $\rho$ to be the largest distance of any $x\in X$ to its nearest neighbor. Formally, $$ \rho = \sup_{x \in X}~ d(x, X \setminus \{x\}). $$ Does this ...
Aryeh's user avatar
  • 10.6k
15 votes
1 answer
645 views

Fixed point theorems for constructive metric spaces?

Banach's fixed point theorem says that if we have a nonempty complete metric space $A$, then any uniformly contractive function $f : A \to A$ it has a unique fixed point $\mu(f)$. However, the proof ...
Neel Krishnaswami's user avatar
11 votes
1 answer
350 views

Is Escardó's metric semantic for PCF+timeouts fully abstract ?

In his 1999 workshop paper "A Metric Model of PCF", Martín Escardó showed that it is possible to give a simple interpretation of PCF in the category of complete ultrametric spaces and ...
Neel Krishnaswami's user avatar