Copertina

Nearly-Tight Bounds for Zonotope Containment and Beyond

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Eisenbrand, Friedrich, Rothvoss, Thomas, Russo, Matteo, Skorupinski, Ruben
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms Metric Geometry
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Lower bounds for the universal TSP on the plane
di: Kravaris, Cosmas
Pubblicazione: (2024)

Unweighted Layered Graph Traversal: Passing a Crown via Entropy Maximization
di: Bai, Xingjian, et al.
Pubblicazione: (2024)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2024)

Fast Nearest Neighbor Search for $\ell_p$ Metrics
di: Krauthgamer, Robert, et al.
Pubblicazione: (2026)

The Power of Recursive Embeddings for $\ell_p$ Metrics
di: Krauthgamer, Robert, et al.
Pubblicazione: (2025)

Time warping with Hellinger elasticity
di: Billig, Yuly
Pubblicazione: (2026)

Fitting trees to $\ell_1$-hyperbolic distances
di: Yim, Joon-Hyeok, et al.
Pubblicazione: (2024)

Random zero sets with local growth guarantees
di: Chang, Alan, et al.
Pubblicazione: (2024)

Time complexity of the Analyst's Traveling Salesman algorithm
di: Ramirez, Anthony, et al.
Pubblicazione: (2022)

O(1)-Distortion Planar Emulators for String Graphs
di: Chang, Hsien-Chih, et al.
Pubblicazione: (2025)

Tight Bounds on the Number of Closest Pairs in Vertical Slabs
di: Biniaz, Ahmad, et al.
Pubblicazione: (2025)

A Tight VC-Dimension Analysis of Clustering Coresets with Applications
di: Cohen-Addad, Vincent, et al.
Pubblicazione: (2025)

Tight Universal Bounds for Partially Presorted Pareto Front and Convex Hull
di: van der Hoog, Ivor, et al.
Pubblicazione: (2025)

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
di: Eisenbrand, Friedrich, et al.
Pubblicazione: (2024)

Nearly Tight Bounds for the Online Sorting Problem
di: Azar, Yossi, et al.
Pubblicazione: (2025)

Dominance for Containment Problems
di: Akram, Waseem, et al.
Pubblicazione: (2022)

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
di: An, Shinwoo, et al.
Pubblicazione: (2024)

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
di: Das, Syamantak, et al.
Pubblicazione: (2024)

Near-tight Bounds for Computing the Fréchet Distance in d-Dimensional Grid Graphs and the Implications for λ-low Dense Curves
di: Conradi, Jacobus, et al.
Pubblicazione: (2026)

Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
di: Fomin, Fedor V., et al.
Pubblicazione: (2025)

Near-Optimal Bounds for Parameterized Euclidean k-means
di: Cohen-Addad, Vincent, et al.
Pubblicazione: (2026)

Nearly Tight Bounds on Testing of Metric Properties
di: Bao, Yiqiao, et al.
Pubblicazione: (2024)

Ortho-Radial Drawing in Near-Linear Time
di: Chang, Yi-Jun
Pubblicazione: (2023)

Upward-Planar Drawings with Bounded Span
di: Angelini, Patrizio, et al.
Pubblicazione: (2026)

Weakly Leveled Planarity with Bounded Span
di: Bekos, Michael, et al.
Pubblicazione: (2024)

Instance and Universally Optimal Bounds for Imprecise Pareto Fronts
di: de Berg, Sarita, et al.
Pubblicazione: (2026)

New Complexity and Algorithmic Bounds for Minimum Consistent Subsets
di: Banik, Aritra, et al.
Pubblicazione: (2024)

Optimal Bounds for Spanners and Tree Covers in Doubling Metrics
di: La, An, et al.
Pubblicazione: (2025)

A Tale of Santa Claus, Hypergraphs and Matroids
di: Davies, Sami, et al.
Pubblicazione: (2018)

On Tight Robust Coresets for $k$-Medians Clustering
di: Huang, Lingxiao, et al.
Pubblicazione: (2025)

Finding a Largest-Area Triangle in a Terrain in Near-Linear Time
di: Cabello, Sergio, et al.
Pubblicazione: (2021)

Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds
di: Huang, Lingxiao, et al.
Pubblicazione: (2023)

Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
di: Duraj, Lech, et al.
Pubblicazione: (2023)

Tight Sampling Bounds for Eigenvalue Approximation
di: Swartworth, William, et al.
Pubblicazione: (2024)

Tight Bounds for Classical Open Addressing
di: Bender, Michael A., et al.
Pubblicazione: (2024)

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
di: Chan, Timothy M., et al.
Pubblicazione: (2025)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
di: de Berg, Mark, et al.
Pubblicazione: (2026)

Optimal Trajectories in Discrete Space with Acceleration Constraints
di: Casteigts, Arnaud, et al.
Pubblicazione: (2026)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
di: Kisfaludi-Bak, Sándor, et al.
Pubblicazione: (2020)

Almost Tight Bounds for Online Hypergraph Matching
di: Tröbst, Thorben, et al.
Pubblicazione: (2024)