Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching

Sujoy Bhore, Timothy M. Chan

Type: Book-Chapter

Publication Date: 2025-01-01

Citations: 0

DOI: https://doi.org/10.1137/1.9781611978322.79

View Publication

Download PDF

Locations

arXiv (Cornell University) - View - PDF
Society for Industrial and Applied Mathematics eBooks - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching	2024	Sujoy Bhore Timothy M. Chan
+ PDF Chat	Fully Dynamic Geometric Vertex Cover and Matching	2024	Sujoy Bhore Timothy M. Chan
+	A tale on guillotine cut	2003	Mihaela Cardei Xiuzhen Cheng Xiaoyan Cheng Ding‐Zhu Du
+	An exact algorithm for a class of geometric set-cover problems	2021	Claudio Contardo Alain Hertz
+	Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set	2023	Arindam Khan Aditya Lonkar Saladi Rahul Aditya Subramanian Andreas Wiese
+ PDF Chat	A Dynamic Programming Framework for Generating Approximately Diverse and Optimal Solutions	2025	Waldo Gálvez Mayank Goswami Arturo Merino G. H. Park Meng-Tsung Tsai Víctor Verdugo
+ PDF Chat	Dynamic Geometric Set Cover, Revisited	2022	Timothy M. Chan Qizheng He Subhash Suri Jie Xue
+	Geometric Algorithms and Linear Programming	1995	Rajeev Motwani Prabhakar Raghavan
+	Exact and Parameterized Algorithms for the Independent Cutset Problem	2024	J. Rauch Dieter Rautenbach Uéverton S. Souza
+	Online Geometric Covering and Piercing	2023	Minati De Saksham Jain Sarat Varma Kallepalli Satyam Singh
+ PDF Chat	Improved approximation algorithms for hitting 3-vertex paths	2019	Samuel Fiorini Gwenaël Joret Oliver Schaudt
+ PDF Chat	Improved Approximation Algorithms for Hitting 3-Vertex Paths	2016	Samuel Fiorini Gwenaël Joret Oliver Schaudt
+ PDF Chat	Parameterized approximation algorithms for packing problems	2016	Meirav Zehavi
+ PDF Chat	New Lower Bound and Algorithms for Online Geometric Hitting Set Problem	2024	Minati De Ratnadip Mandal Satyam Singh
+ PDF Chat	Fast Dynamic Graph Algorithms for Parameterized Problems	2014	Yoichi Iwata Keigo Oka
+	Dynamic Geometric Set Cover and Hitting Set	2020	Pankaj K. Agarwal Hsien-Chih Chang Subhash Suri Allen Xiao Jie Xue
+	Dynamic Geometric Set Cover, Revisited	2021	Timothy M. Chan Qizheng He Subhash Suri Jie Xue
+	An improved fixed parameter tractable algorithm for vertex cover	1999	Ulrike Stege Michael R. Fellows
+	Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles	2020	Monika Henzinger Stefan Neumann Andreas Wiese
+	Solving a class of geometric programming problems by an efficient dynamic model	2012	Alireza Nazemi Elahe Sharifi

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors