63 citations · 168 across the 57 of their papers we have counts for
14 papers · 1 filter
A Deterministic -Approximation for Non-monotone Submodular Maximization under Matroid Constraints
Shengminjie Chen, Kaifeng Lin, Xiaoming Sun +1
Submodular maximization arises in a wide range of combinatorial optimization problems and has been extensively studied from the perspective of approximation algorithms. For maximiz…
Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
Shengminjie Chen, Yiwei Gao, Kaifeng Lin +2
Submodular maximization constitutes a prominent research topic in combinatorial optimization and theoretical computer science, with extensive applications across diverse domains. W…
Efficient Deterministic Algorithms for Maximizing Symmetric Submodular Functions
Zongqi Wan, Jialin Zhang, Xiaoming Sun +1
Symmetric submodular maximization is an important class of combinatorial optimization problems, including MAX-CUT on graphs and hyper-graphs. The state-of-the-art algorithm for the…
Improved Deterministic Streaming Algorithms for Non-monotone Submodular Maximization
Xiaoming Sun, Jialin Zhang, Shuo Zhang
Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. Streaming algorithms for submodule maximiz…
Improved Deterministic Algorithms for Non-monotone Submodular Maximization
Xiaoming Sun, Jialin Zhang, Shuo Zhang +1
Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithm…
Moser-Tardos Algorithm: Beyond Shearer's Bound
Kun He, Qian Li, Xiaoming Sun
In a seminal paper (Moser and Tardos, JACM'10), Moser and Tardos developed a simple and powerful algorithm to find solutions to combinatorial problems in the variable Lov{á}sz Loca…