5 papers
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…
A Lyapunov Framework for Quantum Algorithm Design in Combinatorial Optimization with Approximation Ratio Guarantees
Shengminjie Chen, Ziyang Li, Hongyi Zhou +3
In this work, we develop a framework aiming at designing quantum algorithms for combinatorial optimization problems while providing theoretical guarantees on their approximation ra…
A Unified Complexity-Algorithm Account of Constant-Round QAOA Expectation Computation
Jingheng Wang, Shengminjie Chen, Xiaoming Sun +1
The Quantum Approximate Optimization Algorithm (QAOA) is widely studied for combinatorial optimization and has achieved significant advances both in theoretical guarantees and prac…
Stochastic Quantum Hamiltonian Descent
Sirui Peng, Shengminjie Chen, Xiaoming Sun +1
Stochastic Gradient Descent (SGD) and its variants underpin modern machine learning by enabling efficient optimization of large-scale models. However, their local search nature lim…