Cover Image

Diversity-aware clustering: Computational Complexity and Approximation Algorithms

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Thejaswi, Suhas, Gadekar, Ameet, Ordozgoiti, Bruno, Gionis, Aristides
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Artificial Intelligence Computational Complexity Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
by: Gadekar, Ameet, et al.
Published: (2025)

Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights
by: Gadekar, Ameet, et al.
Published: (2024)

On the Hardness of Approximation of the Fair k-Center Problem
by: Thejaswi, Suhas
Published: (2026)

Label-consistent clustering for evolving data
by: Gadekar, Ameet, et al.
Published: (2025)

Fair Committee Selection under Ordinal Preferences and Limited Cardinal Information
by: Gadekar, Ameet, et al.
Published: (2025)

Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods
by: Blum, Avrim, et al.
Published: (2025)

Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity
by: Feng, Guhao, et al.
Published: (2023)

Exact and Approximate Algorithms for Polytree Learning
by: Harviainen, Juha, et al.
Published: (2026)

On the Parameterized Approximability of (Mergeable) Sum of Radii Clustering
by: Gadekar, Ameet
Published: (2026)

Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint
by: Tran, Tan D., et al.
Published: (2025)

FPT Approximations for Fair Sum of Radii with Outliers and General Norm Objectives
by: Gadekar, Ameet
Published: (2026)

The Computational Complexity of Almost Stable Clustering with Penalties
by: Khodamoradi, Kamyar, et al.
Published: (2025)

Theoretical limitations of multi-layer Transformer
by: Chen, Lijie, et al.
Published: (2024)

Compression Barriers for Autoregressive Transformers
by: Haris, Themistoklis, et al.
Published: (2025)

Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering
by: Gadekar, Ameet, et al.
Published: (2025)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
by: Gopalan, Parikshit, et al.
Published: (2024)

Restless reachability problems in temporal graphs
by: Thejaswi, Suhas, et al.
Published: (2020)

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
by: Banik, Aritra, et al.
Published: (2025)

Learning-Augmented Algorithms for Boolean Satisfiability
by: Attias, Idan, et al.
Published: (2025)

The Sample Complexity of Replicable Realizable PAC Learning
by: Larsen, Kasper Green, et al.
Published: (2026)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
by: Blanc, Guy, et al.
Published: (2024)

Computational-Statistical Tradeoffs from NP-hardness
by: Blanc, Guy, et al.
Published: (2025)

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
by: Alman, Josh, et al.
Published: (2024)

The Computational Complexity of Positive Non-Clashing Teaching in Graphs
by: Ganian, Robert, et al.
Published: (2025)

Efficient and Practical Approximation Algorithms for Advertising in Content Feeds
by: Zhang, Guangyi, et al.
Published: (2025)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
by: Esmer, Barış Can, et al.
Published: (2022)

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

Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification
by: Zhang, Guangyi, et al.
Published: (2026)

Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds
by: Bhore, Sujoy, et al.
Published: (2026)

Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
by: Abbasi, Fateme, et al.
Published: (2023)

Avoiding Obfuscation with Prover-Estimator Debate
by: Brown-Cohen, Jonah, et al.
Published: (2025)

Sorting by Strip Swaps is NP-Hard
by: Roy, Swapnoneel, et al.
Published: (2025)

$\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ via Tree Height Compression
by: Nye, Logan
Published: (2025)

Clustering under Constraints: Efficient Parameterized Approximation Schemes
by: Bhore, Sujoy, et al.
Published: (2025)

Computational Complexity in Property Testing
by: Pinto Jr., Renato Ferreira, et al.
Published: (2025)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
by: Austrin, Per, et al.
Published: (2024)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
by: Buhrman, Harry, et al.
Published: (2025)

Superconstant Inapproximability of Decision Tree Learning
by: Koch, Caleb, et al.
Published: (2024)

Fast decision tree learning solves hard coding-theoretic problems
by: Koch, Caleb, et al.
Published: (2024)