Raichel, BenjaminNo Descriptionhttps://hdl.handle.net/10735.1/6182https://utd-ir.tdl.org/retrieve/5d4ab7ea-2475-4fe3-816b-eb7d8eedd874/2024-06-21T19:49:29Z2024-06-21T19:49:29Z31Viewing the Rings of a Tree: Minimum Distortion Embeddings into TreesNayyeri, A.Raichel, Benjaminhttps://hdl.handle.net/10735.1/86962020-07-10T08:00:55Z2019-01-01T00:00:00Zdc.title: Viewing the Rings of a Tree: Minimum Distortion Embeddings into Trees
dc.contributor.author: Nayyeri, A.; Raichel, Benjamin
dc.description.abstract: We describe a (1 + ε) approximation algorithm for finding the minimum distortion embedding of an npoint metric space, (X, d_X), into a tree with vertex set X. The running time of our algorithm is n²•(∆/ε)^{(O(δopt/ε))2λ+1} parameterized with respect to the spread of X, denoted by ∆, the minimum possible distortion for embedding X into any tree, denoted by δ_{opt}, and the doubling dimension of X, denoted by λ. Hence we obtain a PTAS, provided δ_{opt} is a constant and X is a finite doubling metric space with polynomially bounded spread, for example, a point set with polynomially bounded spread in constant dimensional Euclidean space. Our algorithm implies a constant factor approximation with the same running time when Steiner vertices are allowed. Moreover, we describe a similar (1 + ε) approximation algorithm for finding a tree spanner of (X, d_X) that minimizes the maximum stretch. The running time of our algorithm stays the same, except that δoptmust be interpreted as the minimum stretch of any spanning tree of X. Finally, we generalize our tree spanner algorithm to a (1 + ε) approximation algorithm for computing a minimum stretch tree spanner of a weighted graph, where the running time is parameterized with respect to the maximum degree, in addition to the other parameters above. In particular, we obtain a PTAS for computing minimum stretch tree spanners of weighted graphs, with polynomially bounded spread, constant doubling dimension, and constant maximum degree, when a tree spanner with constant stretch exists. Copyright © 2019 by SIAM.
dc.description: Due to copyright restrictions and/or publisher's policy full text access from Treasures at UT Dallas is limited to current UTD affiliates (use the provided Link to Article).
2019-01-01T00:00:00ZSparse Approximate Conic HullsVan Buskirk, GregoryRaichel, BenjaminRuozzi, Nicholashttps://hdl.handle.net/10735.1/69372019-10-01T08:01:04Zdc.title: Sparse Approximate Conic Hulls
dc.contributor.author: Van Buskirk, Gregory; Raichel, Benjamin; Ruozzi, Nicholas
dc.description.abstract: We consider the problem of computing a restricted nonnegative matrix factorization (NMF) of an m × n matrix X. Specifically, we seek a factorization X ≈ BC, where the k columns of B are a subset of those from X and C ∈ ℝ{^{k×n} _{≥0}} k×n. Equivalently, given the matrix X, consider the problem of finding a small subset, S, of the columns of X such that the conic hull of S ε-approximates the conic hull of the columns of X, i.e., the distance of every column of X to the conic hull of the columns of S should be at most an ε-fraction of the angular diameter of X. If k is the size of the smallest ε-approximation, then we produce an O(k/ε²/³) sized O (ε¹/³)-approximation, yielding the first provable, polynomial time ε-approximation for this class of NMF problems, where also desirably the approximation is independent of n and m. Furthermore, we prove an approximate conic Carathéodory theorem, a general sparsity result, that shows that any column of X can be ε-approximated with an O(1/ε²) sparse combination from S. Our results are facilitated by a reduction to the problem of approximating convex hulls, and we prove that both the convex and conic hull variants are d-SUM-hard, resolving an open problem. Finally, we provide experimental results for the convex and conic algorithms on a variety of feature selection tasks. © 2017 Neural information processing systems foundation. ©2017 Neural Information Processing Systems Foundation. All rights reserved.
dc.description: Includes supplementary material
Geometric Packing Under Nonuniform ConstraintsEne, AlinaHar-Peled, SarielRaichel, Benjamin A.https://hdl.handle.net/10735.1/62432019-04-13T08:46:01Z2018-10-22T00:00:00Zdc.title: Geometric Packing Under Nonuniform Constraints
dc.contributor.author: Ene, Alina; Har-Peled, Sariel; Raichel, Benjamin A.
dc.description.abstract: We study the problem of discrete geometric packing. Here, given weighted regions (say, in the plane) and points (with capacities), one has to pick a maximum weight subset of the regions such that no point is covered more than its capacity. We provide a general framework and an algorithm for approximating the optimal solution for packing in hypergraphs arising out of such geometric settings. Using this framework we get a flotilla of results on this problem (and also on its dual, where one wants to pick a maximum weight subset of the points when the regions have capacities). For example, for the case of fat triangles of similar size, we show an O (1)-approximation and prove that no PTAS is possible.
dc.description: Full text access from Treasures at UT Dallas is restricted to current UTD affiliates.
2018-10-22T00:00:00Z