Cover Image

A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gusain, Rachana, Rahul, Saladi, Subramanian, Aditya
Format:	Preprint
Published:	2025
Subjects:	Computational Geometry Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Optimal-Cost Construction of Shallow Cuttings for 3-D Dominance Ranges in the I/O-Model
by: Nekrich, Yakov, et al.
Published: (2026)

Two Results on LPT: A Near-Linear Time Algorithm and Parcel Delivery using Drones
by: Chandran, L. Sunil, et al.
Published: (2024)

Range Longest Increasing Subsequence and its Relatives
by: S., Karthik C., et al.
Published: (2024)

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
by: Grandoni, Fabrizio, et al.
Published: (2026)

Min-1-Planarity is NP-Hard
by: Okada, Yuto
Published: (2026)

FPT Constant Approximation Algorithms for Colorful Sum of Radii
by: Liu, Shuilian, et al.
Published: (2025)

Computing Maximum Cliques in Unit Disk Graphs
by: Tkachenko, Anastasiia, et al.
Published: (2025)

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

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
by: Tkachenko, Anastasiia, et al.
Published: (2026)

Range Counting Oracles for Geometric Problems
by: Driemel, Anne, et al.
Published: (2025)

Dynamic Unit-Disk Range Reporting
by: Wang, Haitao, et al.
Published: (2024)

Retroactive Monotonic Priority Queues via Range Searching
by: Castro, Lucas, et al.
Published: (2025)

Data Structures for Range Sorted Consecutive Occurrence Queries
by: Akram, Waseem, et al.
Published: (2024)

Hardness of Median and Center in the Ulam Metric
by: Fischer, Nick, et al.
Published: (2025)

Improved Hardness of Approximation for Geometric Bin Packing
by: Ray, Arka, et al.
Published: (2023)

Inapproximability of Maximum Diameter Clustering for Few Clusters
by: Fleischmann, Henry, et al.
Published: (2023)

Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
by: Chan, Timothy M., et al.
Published: (2025)

Computational Hardness of Private Coreset
by: Ghazi, Badih, et al.
Published: (2026)

Hardness of High-Dimensional Linear Classification
by: Munteanu, Alexander, et al.
Published: (2026)

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

A Query-Driven Approach to Space-Efficient Range Searching
by: Fotakis, Dimitris, et al.
Published: (2025)

Guarding Offices with Maximum Dispersion
by: Fekete, Sándor P., et al.
Published: (2025)

Online Maximum Independent Set of Hyperrectangles
by: Advani, Rishi, et al.
Published: (2023)

A Deterministic Partition Tree and Applications
by: Wang, Haitao
Published: (2025)

A Framework for the Design of Efficient Diversification Algorithms to NP-Hard Problems
by: Gálvez, Waldo, et al.
Published: (2025)

A dynamic $(1+\varepsilon)$-spanner for disk intersection graphs
by: de Berg, Sarita, et al.
Published: (2026)

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
by: S, Ajaykrishnan E, et al.
Published: (2025)

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
by: Ebbens, Matthijs, et al.
Published: (2024)

A face cover perspective to $\ell_1$ embeddings of planar graphs
by: Filtser, Arnold
Published: (2019)

A PTAS for Travelling Salesman Problem with Neighbourhoods Over Parallel Line Segments of Similar Length
by: Ghaseminia, Benyamin, et al.
Published: (2025)

On Approximability of $\ell_2^2$ Min-Sum Clustering
by: S., Karthik C., et al.
Published: (2024)

Maximum Polygon Packing: The CG:SHOP Challenge 2024
by: Fekete, Sándor P., et al.
Published: (2024)

A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree
by: Elkin, Yury, et al.
Published: (2021)

Light Spanners with Small Hop-Diameter
by: Bhore, Sujoy, et al.
Published: (2025)

Faster exponential algorithms for cut problems via geometric data structures
by: Kozma, László, et al.
Published: (2025)

Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms
by: Depian, Thomas, et al.
Published: (2025)

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

Learning with Structure: Computing Consistent Subsets on Structurally-Regular Graphs
by: Banik, Aritra, et al.
Published: (2025)

The Peculiarities of Extending Queue Layouts
by: Depian, Thomas, et al.
Published: (2025)

On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
by: Bhore, Sujoy, et al.
Published: (2025)