{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:28:50Z","timestamp":1753885730066,"version":"3.41.2"},"reference-count":22,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"name":"CodeCrafters-Investortools Research Grant","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p> Let [Formula: see text] be a set of [Formula: see text] customers and [Formula: see text] be a set of [Formula: see text] facilities. An [Formula: see text]-gather clustering of [Formula: see text] is a partition of the customers in clusters such that each cluster contains at least [Formula: see text] customers. The [Formula: see text]-gather clustering problem asks to find an [Formula: see text]-gather clustering which minimizes the maximum distance between a pair of customers in a cluster. An [Formula: see text]-gathering of [Formula: see text] to [Formula: see text] is an assignment of each customer [Formula: see text] to a facility [Formula: see text] such that each facility has zero or at least [Formula: see text] customers. The [Formula: see text]-gathering problem asks to find an [Formula: see text]-gathering that minimizes the maximum distance between a customer and his\/her facility. In this work, we consider the [Formula: see text]-gather clustering and [Formula: see text]-gathering problems when the customers and the facilities are lying on a \u201cstar\u201d. We show that the [Formula: see text]-gather clustering problem and the [Formula: see text]-gathering problem with customers and facilities on a star with [Formula: see text] rays can be solved in [Formula: see text] and [Formula: see text] time, respectively. Furthermore, we prove the hardness of a variant of the [Formula: see text]-gathering problem, called the min-max-sum [Formula: see text]-gathering problem, even when the customers and the facilities are on a star. We also study the [Formula: see text]-gathering problem when the customers and the facilities are on a line, and each customer location is uncertain. We show that the [Formula: see text]-gathering problem can be solved in [Formula: see text] and [Formula: see text] time when the customers and the facilities are on a line, and the customer locations are given by piecewise uniform functions of at most [Formula: see text] pieces and \u201cwell-separated\u201d uniform distribution functions, respectively. <\/jats:p>","DOI":"10.1142\/s1793830921501603","type":"journal-article","created":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T14:59:57Z","timestamp":1624892397000},"source":"Crossref","is-referenced-by-count":0,"title":["r-Gatherings on a star and uncertain r-gatherings on a line"],"prefix":"10.1142","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9290-4896","authenticated-orcid":false,"given":"Shareef","family":"Ahmed","sequence":"first","affiliation":[{"name":"Graph Drawing and Information Visualization Laboratory, Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology, Dhaka, Bangladesh"}]},{"given":"Shin-ichi","family":"Nakano","sequence":"additional","affiliation":[{"name":"Gunma University, Kiryu 376-8515, Japan"}]},{"given":"Md. Saidur","family":"Rahman","sequence":"additional","affiliation":[{"name":"Graph Drawing and Information Visualization Laboratory, Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology, Dhaka, Bangladesh"}]}],"member":"219","published-online":{"date-parts":[[2021,8,5]]},"reference":[{"key":"S1793830921501603BIB001","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559816"},{"key":"S1793830921501603BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9903-x"},{"key":"S1793830921501603BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0195-y"},{"key":"S1793830921501603BIB004","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798602"},{"key":"S1793830921501603BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-10564-8_3"},{"key":"S1793830921501603BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-10564-8_3"},{"key":"S1793830921501603BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19647-3_3"},{"key":"S1793830921501603BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.04.040"},{"volume-title":"Facility Location: Applications and Theory","year":"2004","author":"Drezner Z.","key":"S1793830921501603BIB009"},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","year":"1990","author":"Garey M. R.","key":"S1793830921501603BIB010"},{"key":"S1793830921501603BIB011","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892328"},{"key":"S1793830921501603BIB012","first-page":"99","volume-title":"Proc. FCS 2016","author":"Han Y.","year":"2016"},{"key":"S1793830921501603BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.10.010"},{"key":"S1793830921501603BIB014","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892329"},{"key":"S1793830921501603BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-75172-6_1"},{"key":"S1793830921501603BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-10564-8_5"},{"key":"S1793830921501603BIB017","doi-asserted-by":"publisher","DOI":"10.1080\/07408170500216480"},{"key":"S1793830921501603BIB018","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195916600025"},{"key":"S1793830921501603BIB019","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272745"},{"key":"S1793830921501603BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.08.017"},{"key":"S1793830921501603BIB021","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.135"},{"key":"S1793830921501603BIB022","doi-asserted-by":"publisher","DOI":"10.1145\/3084041.3084056"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830921501603","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,2]],"date-time":"2022-08-02T04:50:49Z","timestamp":1659415849000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S1793830921501603"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,5]]},"references-count":22,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.1142\/S1793830921501603"],"URL":"https:\/\/doi.org\/10.1142\/s1793830921501603","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2021,8,5]]},"article-number":"2150160"}}