Search

The current best algorithms for the convex body chasing (CBC) problem in online algorithms use the notion of the Steiner point of a convex set. In particular, the algorithm that always moves to the Steiner point of the request set is O(d) competitive for nested CBC, and this is optimal among memoryless algorithms [Bubeck et al.: Chasing nested convex bodies nearly optimally. In: 31st Annual ACM–SIAM Symposium on Discrete Algorithms (Salt Lake City 2020), pp. 1496–1508. SIAM, Philadelphia (2020)]. A memoryless algorithm coincides with the notion of a selector in functional analysis. The Steiner point is noted for being Lipschitz with respect to the Hausdorff metric, and for achieving the minimal Lipschitz constant possible. It is natural to ask whether every selector with this Lipschitz property yields a competitive algorithm for nested CBC. We answer this question in the negative by exhibiting a selector that yields a non-competitive algorithm for nested CBC but is Lipschitz with respect to Hausdorff distance. Furthermore, we show that being Lipschitz with respect to an L p -type analog of the Hausdorff distance is sufficient to guarantee competitiveness if and only if p = 1 . [ABSTRACT FROM AUTHOR]

Inspired by the seminal works of Khuller et al. (SIAM J. Comput. 25(2), 355–368 (1996)) and Chan (Discrete Comput. Geom. 32(2), 177–194 (2004)) we study the bottleneck version of the Euclidean bounded-degree spanning tree problem. A bottleneck spanning tree is a spanning tree whose largest edge-length is minimum, and a bottleneck degree-K spanning tree is a degree-K spanning tree whose largest edge-length is minimum. Let β K be the supremum ratio of the largest edge-length of the bottleneck degree-K spanning tree to the largest edge-length of the bottleneck spanning tree, over all finite point sets in the Euclidean plane. It is known that β 5 = 1 , and it is easy to verify that β 2 ⩾ 2 , β 3 ⩾ 2 , and β 4 > 1.175 . It is implied by the Hamiltonicity of the cube of the bottleneck spanning tree that β 2 ⩽ 3 . The degree-3 spanning tree algorithm of Ravi et al. (25th Annual ACM Symposium on Theory of Computing, pp. 438–447. ACM, New York (1993)) implies that β 3 ⩽ 2 . Andersen and Ras (Networks 68(4), 302–314 (2016)) showed that β 4 ⩽ 3 . We present the following improved bounds: β 2 ⩾ 7 , β 3 ⩽ 3 , and β 4 ⩽ 2 . As a result, we obtain better approximation algorithms for Euclidean bottleneck degree-3 and degree-4 spanning trees. As parts of our proofs of these bounds we present some structural properties of the Euclidean minimum spanning tree which are of independent interest. [ABSTRACT FROM AUTHOR]

A set of colored graphs are compatible, if for every color i, the number of vertices of color i is the same in every graph. A simultaneous embedding of k compatibly colored graphs, each with n vertices, consists of k planar polyline drawings of these graphs such that the vertices of the same color are mapped to a common set of vertex locations. We prove that simultaneous embedding of k ∈ o (log log n) colored planar graphs, each with n vertices, can always be computed with a sublinear number of bends per edge. Specifically, we show an O (min { c , n 1 - 1 / γ }) upper bound on the number of bends per edge, where γ = 2 ⌈ k / 2 ⌉ and c is the total number of colors. Our bound, which results from a better analysis of a previously known algorithm by Durocher and Mondal (SIAM J Discrete Math 32(4):2703–2719, 2018), improves the bound for k, as well as the bend complexity by a factor of 2 k . The algorithm can be generalized to obtain small universal point sets for colored graphs. We prove that n ⌈ c / b ⌉ vertex locations, where b ≥ 1 , suffice to embed any set of compatibly colored n-vertex planar graphs with bend complexity O(b), where c is the number of colors. [ABSTRACT FROM AUTHOR]

In this paper, we combine the S-iteration process introduced by Agarwal et al. (J. Nonlinear Convex Anal., 8(1), 61–79 2007) with the proximal point algorithm introduced by Rockafellar (SIAM J. Control Optim., 14, 877–898 1976) to propose a new modified proximal point algorithm based on the S-type iteration process for approximating a common element of the set of solutions of convex minimization problems and the set of fixed points of nearly asymptotically quasi-nonexpansive mappings in the framework of CAT(0) spaces and prove the △-convergence of the proposed algorithm for solving common minimization problem and common fixed point problem. Our result generalizes, extends and unifies the corresponding results of Dhompongsa and Panyanak (Comput. Math. Appl., 56, 2572–2579 2008), Khan and Abbas (Comput. Math. Appl., 61, 109–116 2011), Abbas et al. (Math. Comput. Modelling, 55, 1418–1427 2012) and many more. [ABSTRACT FROM AUTHOR]

We present new results on a number of fundamental problems about dynamic geometric data structures: (1) We describe the first fully dynamic data structures with sublinear amortized update time for maintaining (i) the number of vertices or the volume of the convex hull of a 3D point set, (ii) the largest empty circle for a 2D point set, (iii) the Hausdorff distance between two 2D point sets, (iv) the discrete 1-center of a 2D point set, (v) the number of maximal (i.e., skyline) points in a 3D point set. The update times are near n 11 / 12 for (i) and (ii), n 5 / 6 for (iii) and (iv), and n 2 / 3 for (v). Previously, sublinear bounds were known only for restricted "semi-online" settings (Chan in SIAM J. Comput. 32(3), 700–716 (2003)). (2) We slightly improve previous fully dynamic data structures for answering extreme point queries for the convex hull of a 3D point set and nearest neighbor search for a 2D point set. The query time is O (log 2 n) , and the amortized update time is O (log 4 n) instead of O (log 5 n) (Chan in J. ACM 57(3), # 16 (2010); Kaplan et al. in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2495–2504. SIAM, Philadelphia (2017)). (3) We also improve previous fully dynamic data structures for maintaining the bichromatic closest pair between two 2D point sets and the diameter of a 2D point set. The amortized update time is O (log 4 n) instead of O (log 7 n) (Eppstein in Discrete Comput. Geom. 13(1), 111–122 (1995); Chan in J. ACM 57(3), # 16 (2010); Kaplan et al. in 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2495–2504. SIAM, Philadelphia (2017)). [ABSTRACT FROM AUTHOR]

We study numerical integration of smooth functions defined over the |$s$| -dimensional unit cube. A recent work by Dick et al. (2019 , Richardson extrapolation of polynomial lattice rules. SIAM J. Numer. Anal. , 57 , 44–69) has introduced so-called extrapolated polynomial lattice rules, which achieve the almost optimal rate of convergence for numerical integration, and can be constructed by the fast component-by-component search algorithm with smaller computational costs as compared to interlaced polynomial lattice rules. In this paper we prove that, instead of polynomial lattice point sets, truncated higher-order digital nets and sequences can be used within the same algorithmic framework to explicitly construct good quadrature rules achieving the almost optimal rate of convergence. The major advantage of our new approach compared to original higher-order digital nets is that we can significantly reduce the precision of points, i.e. the number of digits necessary to describe each quadrature node. This finding has a practically useful implication when either the number of points or the smoothness parameter is so large that original higher-order digital nets require more than the available finite-precision floating-point representations. [ABSTRACT FROM AUTHOR]