Buchumschlag

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bandyapadhyay, Sayan, Xue, Jie
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Geometry 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

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
von: Bandyapadhyay, Sayan, et al.
Veröffentlicht: (2023)

Extraction Theorems With Small Extraction Numbers
von: Agarwal, Arjun, et al.
Veröffentlicht: (2024)

Exact Subquadratic Algorithm for Many-to-Many Matching on Planar Point Sets with Integer Coordinates
von: Park, Seongbin, et al.
Veröffentlicht: (2026)

The Contiguous Art Gallery Problem is in Θ(n log n)
von: de Berg, Sarita, et al.
Veröffentlicht: (2025)

Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering
von: Nezhad, Sina Bagheri, et al.
Veröffentlicht: (2025)

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2026)

Enclosing Points with Geometric Objects
von: Chan, Timothy M., et al.
Veröffentlicht: (2024)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
von: Bhore, Sujoy, et al.
Veröffentlicht: (2024)

Faster Approximation Scheme for Euclidean $k$-TSP
von: van Wijland, Ernest, et al.
Veröffentlicht: (2023)

Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering
von: Gadekar, Ameet, et al.
Veröffentlicht: (2025)

Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
von: Kar, Debajyoti, et al.
Veröffentlicht: (2026)

Parameterized Approximation of Rectangle Stabbing
von: Chu, Huairui, et al.
Veröffentlicht: (2026)

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
von: Grandoni, Fabrizio, et al.
Veröffentlicht: (2026)

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
von: Lokshtanov, Daniel, et al.
Veröffentlicht: (2024)

Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
von: Galby, Esther, et al.
Veröffentlicht: (2023)

Perfect Matchings and Popularity in the Many-to-Many Setting
von: Kavitha, Telikepalli, et al.
Veröffentlicht: (2024)

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

$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio
von: Soma, Tasuku, et al.
Veröffentlicht: (2025)

Improved Hardness of Approximation for Geometric Bin Packing
von: Ray, Arka, et al.
Veröffentlicht: (2023)

Continuous Map Matching to Paths under Travel Time Constraints
von: Bosch, Yannick, et al.
Veröffentlicht: (2025)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2020)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
von: Huang, Shang-En, et al.
Veröffentlicht: (2016)

Algorithms for Halfplane Coverage and Related Problems
von: Wang, Haitao, et al.
Veröffentlicht: (2024)

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

Sparse Outerstring Graphs Have Logarithmic Treewidth
von: An, Shinwoo, et al.
Veröffentlicht: (2024)

Single-Source Shortest Path Problem in Weighted Disk Graphs
von: An, Shinwoo, et al.
Veröffentlicht: (2025)

Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
von: Chan, Timothy M., et al.
Veröffentlicht: (2026)

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2026)

Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
von: Abbasi, Fateme, et al.
Veröffentlicht: (2023)

Online Algorithms for Geometric Independent Set
von: De, Minati, et al.
Veröffentlicht: (2026)

Range Counting Oracles for Geometric Problems
von: Driemel, Anne, et al.
Veröffentlicht: (2025)

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

Unsolvability and Beyond in Many-To-Many Non-Bipartite Stable Matching
von: Glitzner, Frederik, et al.
Veröffentlicht: (2025)

Approximation Algorithms for Smallest Intersecting Balls
von: Zheng, Jiaqi, et al.
Veröffentlicht: (2024)

Parameterized Geometric Graph Modification with Disk Scaling
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

Adversarially Robust Approximate Furthest Neighbor
von: Banihashem, Kiarash, et al.
Veröffentlicht: (2026)

Approximately: Independence Implies Vertex Cover
von: Har-Peled, Sariel
Veröffentlicht: (2023)

On Approximating the Weighted Region Problem in Square Tessellations
von: Kakimura, Naonori, et al.
Veröffentlicht: (2024)

Data Structures for Approximate Discrete Fréchet Distance
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2022)

Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs
von: Marin, Malory, et al.
Veröffentlicht: (2025)