Open Access Just accepted
Approximation and Heuristic Algorithms for the Priority Facility Location Problem with Outliers
Tsinghua Science and Technology
Available online: 19 March 2024

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
Approximating (mB,mP)-Monotone BP Maximization and Extensions
Tsinghua Science and Technology 2023, 28 (5): 906-915
Published: 19 May 2023

The paper proposes the optimization problem of maximizing the sum of suBmodular and suPermodular (BP) functions with partial monotonicity under a streaming fashion. In this model, elements are randomly released from the stream and the utility is encoded by the sum of partial monotone suBmodular and suPermodular functions. The goal is to determine whether a subset from the stream of size bounded by parameter k subject to the summarized utility is as large as possible. In this work, a threshold-based streaming algorithm is presented for the BP maximization that attains a ((1-κ)/(2-κ)-𝒪(ε))-approximation with 𝒪(1/ε4log3(1/ε)log((2-κ)k/(1-κ)2)) memory complexity, where κ denotes the parameter of supermodularity ratio. We further consider a more general model with fair constraints and present a greedy-based algorithm that obtains the same approximation. We finally investigate this fair model under the streaming fashion and provide a ((1-κ)4/(2-2κ+κ2)2-𝒪(ε))-approximation algorithm.

Open Access Issue
Algorithms for the Prize-Collecting k-Steiner Tree Problem
Tsinghua Science and Technology 2022, 27 (5): 785-792
Published: 17 March 2022

In this paper, we study the prize-collecting k-Steiner tree (PC kST) problem. We are given a graph G=(V,E) and an integer k. The graph is connected and undirected. A vertex rV called root and a subset RV called terminals are also given. A feasible solution for the PC kST is a tree F rooted at r and connecting at least k vertices in R. Excluding a vertex from the tree incurs a penalty cost, and including an edge in the tree incurs an edge cost. We wish to find a feasible solution with minimum total cost. The total cost of a tree F is the sum of the edge costs of the edges in F and the penalty costs of the vertices not in F. We present a simple approximation algorithm with the ratio of 5.9672 for the PC kST. This algorithm uses the approximation algorithms for the prize-collecting Steiner tree (PCST) problem and the k-Steiner tree ( kST) problem as subroutines. Then we propose a primal-dual based approximation algorithm and improve the approximation ratio to 5.

total 3