Sort:
Open Access Issue
Approximation and Heuristic Algorithms for the Priority Facility Location Problem with Outliers
Tsinghua Science and Technology 2024, 29(6): 1694-1702
Published: 20 June 2024
Abstract PDF (2.6 MB) Collect
Downloads:239

In this paper, we propose the Priority Facility Location Problem with Outliers (PFLPO), which is a generalization of both the Facility Location Problem with Outliers (FLPO) and Priority Facility Location Problem (PFLP). As our main contribution, we use the technique of primal-dual to provide a 3-approximation algorithm for the PFLPO. We also give two heuristic algorithms. One of them is a greedy-based algorithm and the other is a local search algorithm. Moreover, we compare the experimental results of all the proposed algorithms in order to illustrate their performance.

Open Access Issue
Multipass Streaming Algorithms for Regularized Submodular Maximization
Tsinghua Science and Technology 2024, 29(1): 76-85
Published: 21 August 2023
Abstract PDF (1.6 MB) Collect
Downloads:40

In this work, we study a k-Cardinality Constrained Regularized Submodular Maximization ( k-CCRSM) problem, in which the objective utility is expressed as the difference between a non-negative submodular and a modular function. No multiplicative approximation algorithm exists for the regularized model, and most works have focused on designing weak approximation algorithms for this problem. In this study, we consider the k-CCRSM problem in a streaming fashion, wherein the elements are assumed to be visited individually and cannot be entirely stored in memory. We propose two multipass streaming algorithms with theoretical guarantees for the above problem, wherein submodular terms are monotonic and nonmonotonic.

Total 2