Author name cluster

Yishuo Shi

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

TCS Journal 2024 Journal Article

Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint

Yishuo Shi
Xiaoyan Lai

The maximization of non-negative monotone submodular functions under a certain constraint is intensively studied. However, there are few works considering the maximization of non-monotone non-submodular functions, which even might be negative. These functions also have many applications, such as optimal marketing for revenue maximization over social networks, budget allocation problems, and Epidemic transmission, etc. In our paper, we discuss the maximization of the non-monotone non-submodular functions under a knapsack constraint, which even might be negative, and explore the performance under the greedy algorithm. We obtain some improved approximate ratios, for the functions with different properties, such as the non-negative weak-monotone weak-submodular functions, and the weak-submodular weak-supermodular functions that might be negative. Moreover, we generalize the results to the functions with weak subadditivity and curvature.

Details DOI

TCS Journal 2024 Journal Article

Greedy algorithm for maximization of semi-monotone non-submodular functions with applications

Yishuo Shi
Hui Zhao

The problem of maximizing submodular set functions has received increasing attention in recent years, and significant improvements have been made, particularly in relation to objective functions that satisfy monotonic submodularity. However, in practice, the objective function may not be monotonically submodular. While greedy algorithms have strong theoretical guarantees for maximizing submodular functions, their performance is barely guaranteed for non-submodular functions. Therefore, in this paper, we investigate the problem of maximizing non-monotone non-submodular functions under knapsack constraints based on the problem of infectious diseases and provides a more sophisticated analysis through the idea of segmentation. Since our definition characterizes the function more elaborately, a better bound, i. e. , a tighter approximation guarantee, is achieved. Finally, we generalize the relevant results for the more general problems.

Details DOI

TCS Journal 2020 Journal Article

A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem

Yishuo Shi
Yingli Ran
Zhao Zhang
Ding-Zhu Du

This paper presents a bicriteria approximation algorithm for the minimum submodular cost partial set multi-cover problem (SCPSMC), the goal of which is to find a minimum cost sub-collection of sets to fully cover q percentage of total profit of all elements, where the cost on sub-collections is a submodular function, and an element e with covering requirement r e is fully covered if it belongs to at least r e picked sets. Assuming that the maximum covering requirement r max = max e ∈ E ⁡ r e is a constant and the cost function is nonnegative and submodular, we give a deterministic ( b / q ε, ( 1 − ε ) ) -bicriteria algorithm for SCPSMC, the output of which fully covers at least ( 1 − ε ) q -percentage of the total profit and the performance ratio is b / q ε, where b = max e ⁡ ( f e r e ) and f e is the number of sets containing element e.

Details DOI

TCS Journal 2014 Journal Article

Approximation algorithm for the minimum weight connected k -subgraph cover problem

Yaping Zhang
Yishuo Shi
Zhao Zhang

A subset F of vertices is called a connected k-subgraph cover ( VCC k ) if every connected subgraph on k vertices contains at least one vertex from F. The minimum weight connected k-subgraph cover problem ( MWVCC k ) has its background in the field of security and supervisory control. It is a generalization of the minimum weight vertex cover problem, and is related with the minimum weight k-path cover problem ( MWVCP k ) which requires that every path on k vertices has at least one vertex from F. A k-approximation algorithm can be easily obtained by LP rounding method. Assuming that the girth of the graph is at least k, we reduce the approximation ratio to k − 1, which is tight for our algorithm.

Details DOI