:: Library Catalog

Buchumschlag

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Kadria, Avi, Roditty, Liam
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	https://arxiv.org/abs/2509.00890
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
von: Kadria, Avi, et al.
Veröffentlicht: (2025)

Improved girth approximation in weighted undirected graphs
von: Kadria, Avi, et al.
Veröffentlicht: (2025)

New algorithms for girth and cycle detection
von: Roditty, Liam, et al.
Veröffentlicht: (2025)

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
von: Roditty, Liam, et al.
Veröffentlicht: (2025)

On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch
von: Kopelowitz, Tsvi, et al.
Veröffentlicht: (2023)

New Diameter Approximations via Distance Oracle Techniques
von: Kirkpatrick, Yael, et al.
Veröffentlicht: (2026)

Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs
von: Roditty, Liam, 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)

Quantum algorithm for approximating the expected value of a random-exist quantified oracle
von: Rotello, Caleb
Veröffentlicht: (2024)

Dynamic Connectivity in Disk Graphs
von: Baumann, Alexander, et al.
Veröffentlicht: (2021)

On $k$-connectivity oracles in $k$-connected graphs
von: Nutov, Zeev
Veröffentlicht: (2026)

Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate $k$-clique counts faster
von: Censor-Hillel, Keren, et al.
Veröffentlicht: (2025)

Convex optimization with $p$-norm oracles
von: Adil, Deeksha, et al.
Veröffentlicht: (2024)

Compact routing schemes in undirected and directed graphs
von: Kadria, Avi, et al.
Veröffentlicht: (2025)

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
von: Dell, Holger, et al.
Veröffentlicht: (2022)

A near-linear time approximation scheme for $(k,\ell)$-median clustering under discrete Fréchet distance
von: Driemel, Anne, et al.
Veröffentlicht: (2025)

Hyper-distance Oracles in Hypergraphs
von: Preti, Giulia, et al.
Veröffentlicht: (2023)

Learning-augmented smooth integer programs with PAC-learnable oracles
von: He, Hao-Yuan, et al.
Veröffentlicht: (2026)

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
von: Ferber, Asaf, et al.
Veröffentlicht: (2025)

Efficient parameterized approximation
von: Kratsch, Stefan, et al.
Veröffentlicht: (2025)

Bicriteria approximation for $k$-edge-connectivity
von: Nutov, Zeev, et al.
Veröffentlicht: (2025)

Improved bicriteria approximation for $k$-edge-connectivity
von: Nutov, Zeev
Veröffentlicht: (2025)

Beyond 2-approximation for k-Center in Graphs
von: Jin, Ce, et al.
Veröffentlicht: (2025)

FPT approximations for Capacitated Sum of Radii and Diameters
von: Filtser, Arnold, et al.
Veröffentlicht: (2024)

On the cut-query complexity of approximating max-cut
von: Plevrakis, Orestis, et al.
Veröffentlicht: (2022)

A simple $(2+ε)$-approximation for knapsack interdiction
von: Weninger, Noah
Veröffentlicht: (2026)

Improved approximation ratio for covering pliable set families
von: Nutov, Zeev
Veröffentlicht: (2024)

Finding the diameter of a tree with distance queries
von: Gerbner, Dániel, et al.
Veröffentlicht: (2025)

Faster single-source shortest paths with negative real weights via proper hop distance
von: Huang, Yufan, et al.
Veröffentlicht: (2024)

A framework for boosting matching approximation: parallel, distributed, and dynamic
von: Mitrović, Slobodan, et al.
Veröffentlicht: (2025)

Testable algorithms for approximately counting edges and triangles in sublinear time and space
von: Eden, Talya, et al.
Veröffentlicht: (2025)

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time
von: Armbruster, Alexander, et al.
Veröffentlicht: (2025)

Better approximation guarantee for Asymmetric TSP
von: Vygen, Jens
Veröffentlicht: (2026)

Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes
von: Velusamy, Santhoshini
Veröffentlicht: (2025)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
von: Kolmogorov, Vladimir
Veröffentlicht: (2023)

Sketching approximations and LP approximations for finite CSPs are related
von: Singer, Noah G., et al.
Veröffentlicht: (2025)

A tight example for approximation ratio 5 for covering small cuts by the primal-dual method
von: Nutov, Zeev
Veröffentlicht: (2025)

An $2\sqrt{k}$-approximation algorithm for minimum power $k$ edge disjoint $st$ -paths
von: Nutov, Zeev
Veröffentlicht: (2022)

Optimal prefix-suffix queries with applications
von: Pissis, Solon P.
Veröffentlicht: (2024)

Deterministically approximating the volume of a Kostka polytope
von: Narayanan, Hariharan, et al.
Veröffentlicht: (2025)