Article
Mathematics, Applied
Majun Shi, Zishen Yang, Wei Wang
Summary: The extension of Minimum Submodular Cover problem to non-submodular potential functions, along with the investigation of Minimum Non-submodular Cover problem with integer-valued and fraction valued potential functions, yield similar performance results. The paper also addresses several real-world applications that can be formulated as Minimum Nonsubmodular Cover problem.
APPLIED MATHEMATICS AND COMPUTATION
(2021)
Article
Computer Science, Interdisciplinary Applications
Hongye Zheng, Suogang Gao, Wen Liu, Weili Wu, Ding-Zhu Du, Bo Hou
Summary: This paper considers the parallel-machine scheduling problem with release dates and submodular rejection penalties, and designs a 2-approximation algorithm based on the primal-dual framework.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2022)
Article
Mathematics
Bich-Ngan T. Nguyen, Phuong N. H. Pham, Van-Vang Le, Vaclav Snasel
Summary: The issue of maximizing submodular functions has gained attention in recent years. This research proposes two streaming algorithms for maximizing a monotone DR-submodular function under cardinality constraints. Experimental results show that the proposed algorithms outperform state-of-the-art algorithms in terms of both the number of queries and the running time, providing solutions with a high objective function value.
Article
Computer Science, Interdisciplinary Applications
Shaojie Tang
Summary: The goal of a sequential decision-making problem is to design an interactive policy that adaptively selects a group of items, each selection is based on the feedback from the past, to maximize the expected utility of selected items. This study proposes to study two variants of adaptive submodular optimization problems and introduces a new class of stochastic functions called worst-case submodular functions. Several applications of the theoretical results are also described.
INFORMS JOURNAL ON COMPUTING
(2022)
Article
Mathematics, Applied
Hiroki Oshima
Summary: The paper introduces improved randomized algorithms for nonmonotone functions in k-submodular maximization problems. The algorithms achieve good approximation results, providing specific algorithm descriptions for k >= 3. Additionally, a specific randomized approximation algorithm is presented for the case when k = 3.
SIAM JOURNAL ON DISCRETE MATHEMATICS
(2021)
Article
Mathematics, Applied
Jiaxuan Zhang, Suogang Gao, Bo Hou, Wen Liu
Summary: This paper considers the group prize-collecting Steiner tree problem with submodular penalties. The goal of the problem is to find an r-rooted tree that minimizes the costs of the edges in the tree plus the penalty cost of the subcollection not spanned by the tree. The main result is a 2I-approximation algorithm for the problem.
COMPUTATIONAL & APPLIED MATHEMATICS
(2022)
Article
Mathematics
Wencheng Wang, Xiaofei Liu
Summary: This paper considers parallel-machine scheduling with release times and submodular penalties and presents a combinatorial 2-approximation algorithm to solve the problem.
Article
Operations Research & Management Science
Xiaofei Liu, Weidong Li
Summary: This paper discusses multiprocessor scheduling with submodular penalties, aiming to minimize the sum of makespan and rejection penalty by finding a subset of rejected jobs and assigning others to machines. Non-combinatorial and combinatorial algorithms are proposed for worst-case guarantee and special case scenarios, respectively.
OPTIMIZATION LETTERS
(2021)
Article
Computer Science, Information Systems
Ruiqi Yang, Suixiang Gao, Lu Han, Gaidi Li, Zhongrui Zhao
Summary: This paper discusses the optimization problem of maximizing the sum of suBmodular and suPermodular functions under a streaming fashion. It proposes a threshold-based streaming algorithm that achieves an approximation of ((1 - kappa)/(2 - kappa) - O(epsilon)) for BP maximization. The paper also considers a more general model with fair constraints and presents a greedy-based algorithm that obtains the same approximation.
TSINGHUA SCIENCE AND TECHNOLOGY
(2023)
Article
Computer Science, Software Engineering
Simon Bruggmann, Rico Zenklusen
Summary: This paper introduces the relaxation and rounding approaches as a versatile tool for constrained submodular function maximization. It proposes a polyhedral viewpoint for designing contention resolution schemes, which avoids explicit dealing with randomization. The framework allows for employing polyhedral techniques and simplifies the construction and analysis of contention resolution schemes.
MATHEMATICAL PROGRAMMING
(2022)
Article
Computer Science, Software Engineering
Chien-Chung Huang, Naonori Kakimura
Summary: In this paper, we propose a (0.4-ε)-approximation algorithm for maximizing a monotone submodular function subject to a knapsack constraint in a streaming setting. The algorithm uses space that is a polynomial of K and ε, improving on the previous best ratio of 0.363-ε.
Article
Computer Science, Artificial Intelligence
Andrew Patterson, Victor Liao, Martha White
Summary: Most value function learning algorithms in reinforcement learning suffer from sensitivity to outliers, which can lead to biased solutions and high-variance gradients. This study proposes a saddlepoint reformulation for robust losses such as Huber Bellman error and Absolute Bellman error, providing more stable gradient-based algorithms for online off-policy prediction and control. The solutions of robust losses are characterized, showing that they can yield notably better solutions than the mean squared Bellman error. These findings contribute to reducing sensitivity to meta-parameters in reinforcement learning.
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE
(2023)
Article
Computer Science, Interdisciplinary Applications
Jing Yuan, Shaojie Tang
Summary: This article focuses on the problem of algorithmic bias in data summarization applications, where the goal is to select a representative and diverse set of data items. The proposed approach introduces fairness-aware algorithms to ensure the proportional representation of different groups. The article also presents constant-factor approximation algorithms for the problem and extends the model to include a global size constraint.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2023)
Article
Robotics
Lifeng Zhou, Vasileios Tzoumas, George J. Pappas, Pratap Tokekar
Summary: In this article, algorithms are designed to protect swarm-robotics applications against sensor denial-of-service attacks, and a distributed robust maximization algorithm is proposed. The distributed approach improves computational speed and achieves tracking performance comparable to centralized algorithms in simulations. Additionally, an improved distributed robust maximization algorithm is introduced to infer attack quantities more accurately.
IEEE TRANSACTIONS ON ROBOTICS
(2022)
Article
Computer Science, Interdisciplinary Applications
Majun Shi, Zishen Yang, Wei Wang
Summary: This paper investigates the Minimum Submodular Cost Submodular Cover problem and the Minimum Submodular Cost Nonsubmodular Cover problem, and analyzes the performances of the greedy algorithm for integer-valued and fraction-valued potential functions.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2023)
Article
Computer Science, Interdisciplinary Applications
Sai Ji, Dachuan Xu, Longkun Guo, Min Li, Dongmei Zhang
Summary: This paper introduces spherical k-means clustering and spherical k-means clustering with penalties, and proposes corresponding approximation algorithms. It also proves that the algorithm on separable instances has a certain approximation ratio.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2022)
Article
Management
Min Li, Dachuan Xu, Dongmei Zhang, Huiling Zhou
Summary: This paper focuses on the parallel seeding algorithm for the k-MPWP problem and provides sufficient analysis on the expected solution quality. The numerical experiment demonstrates the effectiveness of the parallel algorithm for k-means with penalties.
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH
(2022)
Article
Computer Science, Interdisciplinary Applications
Sai Ji, Dachuan Xu, Min Li, Yishui Wang
Summary: This paper introduces two variants of the correlation clustering problem and provides corresponding approximation algorithms. These problems have significant practical implications.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2022)
Article
Computer Science, Software Engineering
Sai Ji, Dachuan Xu, Min Li, Yishui Wang, Dongmei Zhang
Summary: This article studies the problem of maximizing the sum of a constrained submodular and a supermodular function under a cardinality constraint and a p-system constraint. It provides stochastic algorithms for each problem and theoretically proves the approximation ratio of each algorithm. Numerical experiments are conducted to compare the time and quality of the two algorithms in solving the former problem.
CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE
(2023)
Article
Engineering, Multidisciplinary
Min Li, Yishui Wang, Dachuan Xu, Dongmei Zhang
Summary: This paper investigates the functional k-means problem and proposes an O(ln k)-approximation algorithm based on the seeding method, which is shown to be more efficient than the functional k-means clustering algorithm through numerical experiments.
JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION
(2022)
Article
Computer Science, Information Systems
Ruiqi Yang, Dachuan Xu, Longkun Guo, Dongmei Zhang
Summary: This article introduces the problem of maximizing regularized two-stage submodular functions in streams. The aim is to select a subset from an element stream in order to maximize the average maximum value of submodular functions on that subset. The article presents a streaming algorithm with a slightly weaker approximation ratio for this problem.
SCIENCE CHINA-INFORMATION SCIENCES
(2022)
Article
Operations Research & Management Science
Lu Han, Dachuan Xu, Yicheng Xu, Ping Yang
Summary: This paper investigates the individually fair k-center with outliers (IFkCO) problem. A 4-approximation algorithm is proposed and an improved algorithm is developed from a practical perspective. Extensive experiment results are presented to demonstrate the effectiveness of the proposed algorithms.
JOURNAL OF GLOBAL OPTIMIZATION
(2023)
Article
Computer Science, Software Engineering
Zijun Wu, Rolf H. Moehring, Chunying Ren, Dachuan Xu
Summary: This study analyzes the convergence of the price of anarchy in atomic congestion games and provides explicit rates for the convergence. The results show that selfish behavior is justified when the total demand is large.
MATHEMATICAL PROGRAMMING
(2023)
Article
Operations Research & Management Science
Fan Yuan, Da-Chuan Xu, Dong-Lei Du, Dong-Mei Zhang
Summary: This article studies a natural generalization of the typical k-means problem, called the k-means problem with penalties (k-MPWP), and presents a polynomial-time approximation scheme (PTAS) for this problem using the multi-swap local search technique.
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA
(2022)
Article
Operations Research & Management Science
Libing Wang, Han Xiao, Donglei Du, Dachuan Xu
Summary: In this paper, we study profit sharing in independent set games and provide a necessary and sufficient characterization for population monotonic allocation schemes, which can be efficiently verified.
OPERATIONS RESEARCH LETTERS
(2022)
Article
Computer Science, Theory & Methods
Chunying Ren, Zijun Wu, Dachuan Xu, Wenqing Xu
Summary: From a game theoretical perspective, this paper presents a theoretical analysis of deep neural networks. It shows that deep neural networks can be transformed into non-atomic congestion games, and learning the weight and bias vectors is equivalent to computing an optimal solution for the corresponding game.
THEORETICAL COMPUTER SCIENCE
(2023)
Article
Computer Science, Information Systems
Sai Ji, Dachuan Xu, Donglei Du, Ling Gai, Zhongrui Zhao
Summary: This paper introduces a significant application of the Correlation Clustering Problem, which is a clustering problem based on the similarity of data. A new variant of the problem is described and a polynomial time algorithm is presented. The effectiveness of the algorithm is verified through numerical experiments.
TSINGHUA SCIENCE AND TECHNOLOGY
(2022)
Article
Computer Science, Hardware & Architecture
Hongxiang Zhang, Dachuan Xu, Yapu Zhang, Zhenning Zhang
Summary: In this paper, the problem of maximizing a nonmonotone nonnegative one-sided sigma-smooth function G(x) is studied. Two classes of parallel algorithms are proposed for a downwards-closed basis polyhedron constraint under deterministic and random settings. For the deterministic nonmonotone OSS problem, the Jump-Start Parallel Frank Wolfe (JSPFW) algorithm is designed to obtain an approximation solution. For the stochastic OSS problem, the Stochastic Parallel Frank Wolfe (SPFW) algorithm is designed to get an approximation solution.
COMPUTERS & ELECTRICAL ENGINEERING
(2023)
Article
Computer Science, Interdisciplinary Applications
Sai Ji, Yinhong Dong, Donglei Du, Dongzhao Wang, Dachuan Xu
Summary: This paper introduces a new generalization of the correlation clustering problem called the lower bounded correlation clustering problem (LBCorCP). Three algorithms are proposed to solve this problem. The first algorithm is a random algorithm for instances with fewer positive edges. The second algorithm treats the set V itself as a cluster and works well on instances with fewer negative edges. The last algorithm is an LP-rounding based iterative algorithm for instances with fewer negative edges. Simulations are conducted to evaluate the performance of the algorithms.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2023)
Article
Engineering, Multidisciplinary
Xin Sun, Dachuan Xu, Dongmei Zhang, Yang Zhou
Summary: In this paper, we propose an adaptive algorithm for maximizing non-submodular set functions under a single matroid constraint. The algorithm is based on the continuous greedy approach and measures the deviation of the set function from submodularity using the generic submodularity ratio gamma. We prove the approximation ratio of the algorithm and provide a solution for converting the fractional solution to a discrete one.
JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION
(2023)
