Approximation algorithms for orthogonal line centers

DOI10.1016/j.dam.2023.05.014zbMath1516.68120MaRDI QIDQ6166042

Sandip Das, Joydeep Mukherjee, Arun Kumar Das

Publication date: 2 August 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

combinatorial optimizationfacility locationgeometric optimizationbi-criteria approximationorthogonal line centers

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Cites Work

• Fixed-parameter tractability and lower bounds for stabbing problems
• Approximation algorithms for a \(k\)-line center
• A (\(1+{\varepsilon}\))-approximation algorithm for 2-line-center
• Approximating \(k\)-orthogonal line center
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• SEPARATING POINTS BY AXIS-PARALLEL LINES
• On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
• Bi-criteria linear-time approximations for generalized k-mean/median/center
• Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
• State of the Art—Location on Networks: A Survey. Part I: The p-Center and p-Median Problems
• Approximation algorithms for projective clustering
• The two-line center problem from a polar view: a new algorithm and data structure

This page was built for publication: Approximation algorithms for orthogonal line centers