Cited By
View all- Ahn TChung CAhn HBae SCheong OYoon S(2024)Minimum-Width Double-Slabs and Widest Empty Slabs in High DimensionsLATIN 2024: Theoretical Informatics10.1007/978-3-031-55598-5_20(303-317)Online publication date: 18-Mar-2024
Approximation algorithms for orthogonal line centers
References
[1]
Agarwal P.K., Procopiuc C.M., Approximation algorithms for projective clustering, J. Algorithms 46 (2) (2003) 115–139.
[2]
Agarwal P.K., Procopiuc C.M., Varadarajan K.R., A (1+ ɛ)-approximation algorithm for 2-line-center, Comput. Geom. 26 (2) (2003) 119–128.
[3]
Agarwal P.K., Procopiuc C.M., Varadarajan K.R., Approximation algorithms for a k-Line center, Algorithmica 42 (3) (2005) 221–230.
[4]
Aggarwal C.C., Wolf J.L., Yu P.S., Procopiuc C., Park J.S., Fast algorithms for projected clustering, SIGMOD Rec. (1999) 61–72.
[5]
Aggarwal C.C., Yu P.S., Finding generalized projected clusters in high dimensional spaces, in: Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, SIGMOD ’00, Association for Computing Machinery, 2000, pp. 70–81.
[6]
Agrawal R., Gehrke J., Gunopulos D., Raghavan P., Automatic subspace clustering of high dimensional data for data mining applications, in: Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, 27, SIGMOD ’98, Association for Computing Machinery, 1998, pp. 94–105.
[7]
Boeing G., Urban spatial order: street network orientation, configuration, and entropy, Appl. Netw. Sci. 4 (1) (2019) 67.
[8]
Călinescu G., Dumitrescu A., Karloff H., Wan P.-J., Separating points by axis-parallel lines, Internat. J. Comput. Geom. Appl. 15 (06) (2005) 575–590.
[9]
Chakraborty B., Das A.K., Das S., Mukherjee J., Approximating k-orthogonal line center, in: Combinatorial Optimization and Applications, Springer International Publishing, 2020, pp. 47–60.
[10]
Dom M., Fellows M.R., Rosamond F.A., Parameterized complexity of stabbing rectangles and squares in the plane, in: WALCOM: Algorithms and Computation, Springer Berlin Heidelberg, 2009, pp. 298–309.
[11]
Faber A., Förstner W., Detection of dominant orthogonal road structures in small scale imagery, Int. Arch. Photogramm. Remote Sens. 33 (B3/1; PART 3) (2000) 274–281.
[12]
Feldman D., Fiat A., Sharir M., Segev D., Bi-criteria linear-time approximations for generalized k-Mean/Median/Center, in: Proceedings of the Twenty-Third Annual Symposium on Computational Geometry, SCG ’07, Association for Computing Machinery, 2007, pp. 19–26.
[13]
Gaur D.R., Ibaraki T., Krishnamurti R., Constant ratio approximation algorithms for the rectangle stabbing problem and the rectilinear partitioning problem, J. Algorithms 43 (1) (2002) 138–152.
[14]
Giannopoulos P., Knauer C., Rote G., Werner D., Fixed-parameter tractability and lower bounds for stabbing problems, Comput. Geom. 46 (7) (2013) 839–860. EuroCG 2009.
[15]
Guruswami V., Saket R., On the inapproximability of vertex cover on k-Partite k-Uniform hypergraphs, in: Automata, Languages and Programming, Springer Berlin Heidelberg, 2010, pp. 360–371.
[16]
Jaromczyk J.W., Kowaluk M., The two-line center problem from a polar view: A new algorithm and data structure, in: Proceedings of the 4th International Workshop on Algorithms and Data Structures, WADS ’95, Springer-Verlag, 1995, pp. 13–25.
[17]
F. Koushanfar, S. Slijepcevic, M. Potkonjak, A. Sangiovanni-Vincentelli, Error-tolerant multimodal sensor fusion, in: IEEE CAS Workshop on Wireless Communication and Networking, 2002, pp. 5–6.
[18]
Lovász L., Plummer M.D., Matching Theory, Vol. 367, American Mathematical Soc., 2009.
[19]
Procopiuc C.M., Jones M., Agarwal P.K., Murali T.M., A Monte Carlo algorithm for fast projective clustering, in: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, SIGMOD ’02, Association for Computing Machinery, 2002, pp. 418–427.
[20]
Renner W.D., Pugh N.O., Ross D.B., Berg R.E., Hall D.C., An algorithm for planning stereotactic brain implants, Int. J. Radiat. Oncol. Biol. Phys. 13 (4) (1987) 631–637.
[21]
Tansel B.C., Francis R.L., Lowe T.J., State of the art-location on networks: A survey. Part I: The p-Center and p-Median problems, Manage. Sci. 29 (4) (1983).
[22]
Zanjirani Farahani R., Hekmatfar M., Facility location: Concepts, models, algorithms and case studies, Media (2009).
Recommendations
Approximating k-Orthogonal Line Center
Combinatorial Optimization and ApplicationsAbstractk-orthogonal line center problem computes a set of k axis-parallel lines for a given set of n points such that the maximum among the distances between each point and its nearest line is minimized. In this paper, we design a deterministic bi-...
Improved Combinatorial Algorithms for Facility Location Problems
We present improved combinatorial approximation algorithms for the uncapacitated facility location problem. Two central ideas in most of our results are cost scaling and greedy improvement. We present a simple greedy local search algorithm which ...
Approximation Algorithms for Orthogonal Line Centers
Algorithms and Discrete Applied MathematicsAbstractk orthogonal line center problem computes a set of k axis-parallel lines for a given set of points in 2D such that the maximum among the distance between each point to its nearest line is minimized. A 2-factor approximation algorithm and a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Elsevier B.V.
Publisher
Elsevier Science Publishers B. V.
Netherlands
Publication History
Published: 30 October 2023
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 26 Dec 2024
Other Metrics
Citations
Cited By
View all- Ahn TChung CAhn HBae SCheong OYoon S(2024)Minimum-Width Double-Slabs and Widest Empty Slabs in High DimensionsLATIN 2024: Theoretical Informatics10.1007/978-3-031-55598-5_20(303-317)Online publication date: 18-Mar-2024