Buchumschlag

A Simple PTAS for Weighted $k$-means and Sensor Coverage

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Pareek, Akash, Shit, Supratim
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

A PTAS for Weighted Triangle-free 2-Matching
von: Bosch-Calvo, Miguel, et al.
Veröffentlicht: (2026)

Greedy BST on Permutation Initial Tree
von: Pareek, Akash
Veröffentlicht: (2024)

Validating a PTAS for Triangle-Free 2-Matching via a Simple Decomposition Theorem
von: Kobayashi, Yusuke, et al.
Veröffentlicht: (2024)

Non-Adaptive Evaluation of $k$-of-$n$ Functions: Tight Gap and a Unit-Cost PTAS
von: Nielsen, Mads Anker, et al.
Veröffentlicht: (2025)

Deterministic Coreset for Lp Subspace
von: Chhaya, Rachit, et al.
Veröffentlicht: (2026)

Counting Patterns in Degenerate Graphs in Constant Space
von: Komarath, Balagopal, et al.
Veröffentlicht: (2025)

NP-Hardness and a PTAS for the Pinwheel Problem
von: Kleinberg, Robert, et al.
Veröffentlicht: (2026)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
von: Bartlmae, Simon, et al.
Veröffentlicht: (2024)

Maximum Coverage $k$-Antichains and Chains: A Greedy Approach
von: Cáceres, Manuel, et al.
Veröffentlicht: (2025)

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

Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts
von: Fischer, Nick, et al.
Veröffentlicht: (2026)

Local Search k-means++ with Foresight
von: Conrads, Theo, et al.
Veröffentlicht: (2024)

Ads that Stick: Near-Optimal Ad Optimization through Psychological Behavior Models
von: Darmasubramanian, Kailash Gopal, et al.
Veröffentlicht: (2025)

Weighted $k$-Server Admits an Exponentially Competitive Algorithm
von: Bijoy, Adithya, et al.
Veröffentlicht: (2025)

Semi-Streaming Algorithms for Weighted $k$-Disjoint Matchings
von: Ferdous, S M, et al.
Veröffentlicht: (2023)

Fast $k$-means Seeding Under The Manifold Hypothesis
von: Shah, Poojan, et al.
Veröffentlicht: (2026)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
von: S., Karthik C., et al.
Veröffentlicht: (2024)

Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets
von: Nederlof, Jesper
Veröffentlicht: (2025)

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
von: D'Angelo, Gianlorenzo, et al.
Veröffentlicht: (2025)

Bounds on Longest Simple Cycles in Weighted Directed Graphs via Optimum Cycle Means
von: Dasdan, Ali
Veröffentlicht: (2025)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
von: Fischer, Nick, et al.
Veröffentlicht: (2024)

Optimizing Administrative Divisions: A Vertex $k$-Center Approach for Edge-Weighted Road Graphs
von: Daugulis, Peteris
Veröffentlicht: (2025)

A Faster $k$-means++ Algorithm
von: Liang, Jiehao, et al.
Veröffentlicht: (2022)

On Line-Separable Weighted Unit-Disk Coverage and Related Problems
von: Liu, Gang, et al.
Veröffentlicht: (2024)

A Constant-Approximation Algorithm for Budgeted Sweep Coverage with Mobile Sensors
von: Liang, Wei, et al.
Veröffentlicht: (2024)

Simple Quantum Algorithm for Approximate $k$-Mismatch Problem
von: Habib, Ruhan, et al.
Veröffentlicht: (2025)

FPT Approximations for Connected Maximum Coverage
von: Inamdar, Tanmay, et al.
Veröffentlicht: (2026)

Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back
von: Manurangsi, Pasin
Veröffentlicht: (2024)

Online Drone Coverage of Targets on a Line
von: Dobrev, Stefan, et al.
Veröffentlicht: (2026)

Dominating Set with Quotas: Balancing Coverage and Constraints
von: Chatterjee, Sobyasachi, et al.
Veröffentlicht: (2026)

Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures
von: Ene, Alina, et al.
Veröffentlicht: (2025)

Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
von: Inamdar, Tanmay, et al.
Veröffentlicht: (2024)

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

Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems
von: Song, Shihong, et al.
Veröffentlicht: (2024)

A Simple Analysis of Ranking in General Graphs
von: Derakhshan, Mahsa, et al.
Veröffentlicht: (2025)

A Simple Algorithm for Trimmed Multipoint Evaluation
von: Fischer, Nick, et al.
Veröffentlicht: (2025)

A Simple Algorithm for Clustering Discrete Distributions
von: Mitra, Pradipta
Veröffentlicht: (2026)

A Simple Algorithm for Dynamic Carpooling with Recourse
von: Efron, Yuval, et al.
Veröffentlicht: (2024)

A Simple Dynamic Spanner via APSP
von: Kyng, Rasmus, et al.
Veröffentlicht: (2024)

A Simple and Fast Algorithm for Fair Cuts
von: Li, Jason, et al.
Veröffentlicht: (2024)