74 citations · 78 across the 11 of their papers we have counts for
13 papers
Quantum Submodular Maximization
Yonggang Jiang, Xiaoming Sun, Penghui Yao +3
We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constr…
Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy
Zongqi Wan, Zhijie Zhang
We study adversarial bandit maximization of monotone submodular functions under a matroid constraint. For a rank- matroid on elements, we give a randomized oracle-polynomial…
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…
Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits
Zongqi Wan, Jialin Zhang, Wei Chen +2
We investigate the online bandit learning of the monotone multi-linear DR-submodular functions, designing the algorithm that attains of $(1…
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…
Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets
Zongqi Wan, Zhijie Zhang, Tongyang Li +2
Multi-arm bandit (MAB) and stochastic linear bandit (SLB) are important models in reinforcement learning, and it is well-known that classical algorithms for bandits with time horiz…
Online Influence Maximization under the Independent Cascade Model with Node-Level Feedback
Zhijie Zhang, Wei Chen, Xiaoming Sun +1
We study the online influence maximization (OIM) problem in social networks, where the learner repeatedly chooses seed nodes to generate cascades, observes the cascade feedback, an…
Network Inference and Influence Maximization from Samples
Zhijie Zhang, Wei Chen, Xiaoming Sun +1
Influence maximization is the task of selecting a small number of seed nodes in a social network to maximize the influence spread from these seeds. It has been widely investigated…
Learning N:M Fine-grained Structured Sparse Neural Networks From Scratch
Aojun Zhou, Yukun Ma, Junnan Zhu +5
Sparsity in Deep Neural Networks (DNNs) has been widely studied to compress and accelerate the models on resource-constrained environments. It can be generally categorized into uns…
Optimization from Structured Samples for Coverage Functions
Wei Chen, Xiaoming Sun, Jialin Zhang +1
We revisit the optimization from samples (OPS) model, which studies the problem of optimizing objective functions directly from the sample data. Previous results showed that we can…
Simple Deterministic Approximation for Submodular Multiple Knapsack Problem
Xiaoming Sun, Jialin Zhang, Zhijie Zhang
Submodular maximization has been a central topic in theoretical computer science and combinatorial optimization over the last decades. Plenty of well-performed approximation algori…
Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol
Xiaohui Bei, Xiaoming Sun, Hao Wu +3
The classical cake cutting problem studies how to find fair allocations of a heterogeneous and divisible resource among multiple agents. Two of the most commonly studied fairness c…
A Linear Algorithm for Finding the Sink of Unique Sink Orientations on Grids
Xiaoming Sun, Jialin Zhang, Zhijie Zhang
An orientation of a grid is called unique sink orientation (USO) if each of its nonempty subgrids has a unique sink. Particularly, the original grid itself has a unique global sink…