Spaces that can be ordered effectively: virtually free groups and hyperbolicity

Nilpotent groups (20F18) Geometric group theory (20F65) Hyperbolic groups and nonpositively curved groups (20F67) Asymptotic properties of groups (20F69) Combinatorial optimization (90C27)

Abstract: We study asymptotic invariants of metric spaces, defined in terms of the travelling salesman problem, and our goal is to classify groups and spaces depending on how well they can be ordered in this context. We characterize virtually free groups as those admitting an order which has some efficiency on

4

-point subsets. We show that all

d e l t a

-hyperbolic spaces can be ordered extremely efficiently, for the question when the number of points of a subset tends to

i n f t y

.

Review text

Let \((M,d)\), be a metric space and \(X\) a finite subset of \(M\). We denote by \(l_{\mathrm{opt}}(X)\) the minimal length of a path which visits all points of \(X\). Assume that \(T\) is a total order on \(M\). For a finite subset \(X\subset M\), we consider the restriction of order \(T\) on \(M\) and enumerate the points of \(X\) accordingly: \(x_1\leq_{T} x_2\leq_{T} x_3\leq_{T}\dots\leq_{T} x_{k}\) where \(k = \# X\). We denote by \(l_T(X)\) the length of the corresponding path \(l_{T}(X):= d(x_1,x_2) + d(x_2,x_3) + \dots + d(x_{k-1},x_k)\). Definition 1.1. Given an order space \(M = (M,d,T)\) containing at least two points and \(k\geq 1\), we define the order ratio function \[ \operatorname{OR}_{M,T}(k):= \sup_{X\subset M\mid 2\leq\# X\leq k+1}\frac{l_{T}(X)}{l_{\mathrm{opt}}(X)}. \] If \(M\) consists of a single point, then the supremum in the definition above is taken over an empty set. We use in this case the convention that \(\operatorname{OR}_{M,T}(k) = 1\) for all \(k\geq 1\). For an (unordered) metric space \((M,d)\), we also define the \textit{order ratio function} as \(\operatorname{OR}_{M}(k) := \inf_{T} \operatorname{OR}_{M,T}(k)\). Given an algorithm to find an approximate solution of an optimization problem, the worst case of the ratio between the value provided by this algorithm and the optimal value is called the \textit{competitive ratio.} The traveling salesman problem is a problem to find a cycle of minimum total length that visits each of \(k\) given points. \textit{L. K. Platzman} and \textit{J. J. Bartholdi III} [J. Assoc. Comput. Mach. 36, No. 4, 719--737 (1989; Zbl 0697.68047)] introduced the idea to order all points of a metric space and then, given a \(k\)-point subset, visit its points in the corresponding order. Such an approach is called the \textit{universal travelling salesman problem}. In contrast with previous works on the competitive ratio of universal travelling salesman problem, the authors are interested not only in this asymptotic behaviour but also in particular values of \(\operatorname{OR}(k)\). Definition 1.2. Let \(M\) be a metric space, containing at least two points, and let \(T\) be an order on \(M\). We say that the order breakpoint \(\operatorname{Br}(M,T) = s\) if \(s\) is the smallest integer such that \(\operatorname{OR}_{M,T}(s) < s\). If such \(s\) does not exists, we say that \(\operatorname{Br}(M,T) = \infty\). In particular, \(\operatorname{Br}(M,T) = 2\) for a one-point space \(M\). Moreover, we define \(\operatorname{Br}(M)\) as the minimum over all orders \(T\) on \(M\). Given an order on \(M\), the order breakpoint describes the minimal value \(k\) for which using this order as a universal order for the travelling salesman problem has some efficiency on \((k+1)\)-point subset. From the definition, \(\operatorname{Br}(M,T)\geq 2\) for any \(M\) and \(\operatorname{Br}(M,T) = 2\) if \(M\) is finite. The order breakpoint is quasi-isometric invariant for uniformly discrete metric spaces, hence it is well-defined for finitelly generated groups. In the paper under review, the following are proved: Theorem 4.8. Let \(G\) be a finitely generated group. Then \(G\) is virtually free iff \(\operatorname{Br}(G) \leq 3\) (in other words, if \(G\) admits an order \(T\) with \(\operatorname{Br}(G,T) \leq 3\).) Theorem 5.10. Let \(M\) be a \(\delta\)-hyperbolic graph of bounded degree. Then there exsits an order \(T\) and a constant \(C\) such that for all \(k\geq 1\) \[ \operatorname{OR}_{M,T}(k)\leq C. \]

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Spaces that can be ordered effectively: virtually free groups and hyperbolicity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6163406)