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.

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 $\mathrm{(}\mathrm{(}\mathrm{1}\mathrm{-}\kappa \mathrm{)}\mathrm{/}\mathrm{(}\mathrm{2}\mathrm{-}\kappa \mathrm{)}\mathrm{-}𝒪\mathsf{}\mathrm{(}\epsilon \mathrm{)}\mathrm{)}$-approximation with $𝒪\mathsf{}\mathrm{(}\mathrm{1}\mathrm{/}{\epsilon }^{\mathrm{4}}\mathsf{}{\log }^{\mathrm{3}}\mathsf{}\mathrm{(}\mathrm{1}\mathrm{/}\epsilon \mathrm{)}\mathsf{}\log \mathsf{}\mathrm{(}\mathrm{(}\mathrm{2}\mathrm{-}\kappa \mathrm{)}\mathsf{}k\mathrm{/}{\mathrm{(}\mathrm{1}\mathrm{-}\kappa \mathrm{)}}^{\mathrm{2}}\mathrm{)}\mathrm{)}$ memory complexity, where $\kappa$ 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 $\mathrm{(}{\mathrm{(}\mathrm{1}\mathrm{-}\kappa \mathrm{)}}^{\mathrm{4}}\mathrm{/}{\mathrm{(}\mathrm{2}\mathrm{-}\mathrm{2}\mathsf{}\kappa \mathrm{+}{\kappa }^{\mathrm{2}}\mathrm{)}}^{\mathrm{2}}\mathrm{-}𝒪\mathsf{}\mathrm{(}\epsilon \mathrm{)}\mathrm{)}$-approximation algorithm.

In this paper, we study the prize-collecting $k$-Steiner tree (PC $k$ST) problem. We are given a graph $G\mathrm{=}\mathrm{(}V\mathrm{,}E\mathrm{)}$ and an integer $k$. The graph is connected and undirected. A vertex $r\mathrm{\in }V$ called root and a subset $R\mathrm{\subseteq }V$ called terminals are also given. A feasible solution for the PC $k$ST 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 $\mathrm{5.9672}$ for the PC $k$ST. This algorithm uses the approximation algorithms for the prize-collecting Steiner tree (PCST) problem and the $k$-Steiner tree ( $k$ST) problem as subroutines. Then we propose a primal-dual based approximation algorithm and improve the approximation ratio to $\mathrm{5}$.