Xinlan Xia

dblp:386/3837 · DBLP profile ↗
← Back
3ranked-venue papers
3as first author
3since 2021 · last 2025
0009-0006-3366-9845ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 first-author · 2 since 2021Applied, interdisciplinary, general and emerging computing · 1 · 1 first-author · 1 since 2021
YearPublicationVenuePosition
2025 An approximation algorithm for the parity-constrained k-supplier problem
abstract
This paper studies the parity-constrained k -supplier (PAR k -supplier) problem, which extends the well-known k -supplier problem. In the PAR k -supplier problem, we are given a set of vertices in a metric space with distances and an integer k . The vertex set is partitioned into a facility set and a client set. Each facility has an odd or even parity requirement. The objective is to select at most k facilities to open and assign each client to an open facility, ensuring that the number of clients assigned to each open facility matches its parity requirement, while also minimizing the maximum distance of any client to its assigned facility. As our main contribution, we design the first constant-factor 9-approximation algorithm for the parity-constrained k -supplier problem. The algorithm is divided into two main phases. In the first phase, we determine the initial set of open facilities with a maximum cardinality of k and the assignment of all the clients. There may include some so-called invalid facilities that do not meet their parity requirements under the initial assignment. In the second phase, we find a matching based on the invalid facilities and reassign some clients accordingly to obtain a feasible solution.
Xinlan Xia, Lili Mei
Theor. Comput. Sci.1
2024 Parity-Constrained Weighted k-Center
Xinlan Xia, Lili Mei
AAIM (1)1
2024 Parity-Constrained k-Supplier Problem
Xinlan Xia, Lili Mei
IJTCS-FAW1