Buchumschlag

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bathie, Gabriel, Lagarde, Guillaume
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Analyzing and Leveraging the $k$-Sensitivity of LZ77
von: Bathie, Gabriel, et al.
Veröffentlicht: (2026)

Weakly Approximating Knapsack in Subquadratic Time
von: Chen, Lin, et al.
Veröffentlicht: (2025)

Approximately Counting Knapsack Solutions in Subquadratic Time
von: Feng, Weiming, et al.
Veröffentlicht: (2024)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
von: Mao, Xiao, et al.
Veröffentlicht: (2026)

Approximate Distance Sensitivity Oracles in Subquadratic Space
von: Bilò, Davide, et al.
Veröffentlicht: (2023)

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
von: Mao, Xiao
Veröffentlicht: (2023)

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
von: Cheng, Siu-Wing, et al.
Veröffentlicht: (2025)

Pattern Matching with Mismatches and Wildcards
von: Bathie, Gabriel, et al.
Veröffentlicht: (2024)

Internal Pattern Matching in Small Space and Applications
von: Bathie, Gabriel, et al.
Veröffentlicht: (2024)

Small Space Encoding and Recognition of $k$-Palindromic Prefixes
von: Bathie, Gabriel, et al.
Veröffentlicht: (2024)

Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares
von: Bathie, Gabriel, et al.
Veröffentlicht: (2023)

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
von: Ebbens, Matthijs, et al.
Veröffentlicht: (2024)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
von: Bille, Philip, et al.
Veröffentlicht: (2022)

Fréchet Distance in Subquadratic Time
von: Cheng, Siu-Wing, et al.
Veröffentlicht: (2024)

A Subquadratic Bound for Online Bisection
von: Bienkowski, Marcin, et al.
Veröffentlicht: (2023)

Computing Flows in Subquadratic Space
von: Brand, Jan van den, et al.
Veröffentlicht: (2026)

The Trichotomy of Regular Property Testing
von: Bathie, Gabriel, et al.
Veröffentlicht: (2025)

Longest Common Extensions with Wildcards: Trade-off and Applications
von: Bathie, Gabriel, et al.
Veröffentlicht: (2024)

Streaming Edge Coloring with Subquadratic Palette Size
von: Chechik, Shiri, et al.
Veröffentlicht: (2023)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

Decremental $(1+ε)$-Approximate Maximum Eigenvector: Dynamic Power Method
von: Adil, Deeksha, et al.
Veröffentlicht: (2024)

Fitting Tree Metrics and Ultrametrics in Data Streams
von: Carmel, Amir, et al.
Veröffentlicht: (2025)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2024)

Subquadratic Submodular Maximization with a General Matroid Constraint
von: Kobayashi, Yusuke, et al.
Veröffentlicht: (2024)

Preprocessed 3SUM for Unknown Universes with Subquadratic Space
von: Kirkpatrick, Yael, et al.
Veröffentlicht: (2026)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
von: Georgiadis, Loukas, et al.
Veröffentlicht: (2026)

Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
von: Paul-Pena, Daniel, et al.
Veröffentlicht: (2024)

A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
von: Bringmann, Karl, et al.
Veröffentlicht: (2024)

A $(5/3+ε)$-Approximation for Tricolored Non-crossing Euclidean TSP
von: Baligács, Júlia, et al.
Veröffentlicht: (2024)

Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
von: Solomon, Shay, et al.
Veröffentlicht: (2023)

Subquadratic Counting via Perfect Marginal Sampling
von: Chen, Xiaoyu, et al.
Veröffentlicht: (2026)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
von: Anand, Aditya, et al.
Veröffentlicht: (2024)

Classes Testable with $O(1/ε)$ Queries for Small $ε$ Independent of the Number of Variables
von: Bshouty, Nader H., et al.
Veröffentlicht: (2026)

Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more
von: Karczmarz, Adam, et al.
Veröffentlicht: (2024)

Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue
von: Arenas, Marcelo, et al.
Veröffentlicht: (2024)

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

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
von: Gholizadeh, Hossein, et al.
Veröffentlicht: (2025)