Query：
学者姓名：张智杰
Refining：
Year
Type
Indexed by
Source
Complex
Former Name
Co-
Language
Clean All
Abstract ：
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 problem over general constraints has an approximation ratio of 0.432 [16]. The algorithm applies the canonical continuous greedy technique that involves a sampling process. It, therefore, suffers from high query complexity and is inherently randomized. In this paper, we present several efficient deterministic algorithms for maximizing a symmetric submodular function under various constraints. Specifically, for the cardinality constraint, we design a deterministic algorithm that attains a 0.432 ratio and uses O(kn) queries. Previously, the best deterministic algorithm attains a 0.385−ϵ ratio and uses [Formula presented] queries [12]. For the matroid constraint, we design a deterministic algorithm that attains a 1/3−ϵ ratio and uses O(knlogϵ−1) queries. Previously, the best deterministic algorithm can also attain 1/3−ϵ ratio but it uses much larger O(ϵ−1n4) queries [24]. For the packing constraints with a large width, we design a deterministic algorithm that attains a 0.432−ϵ ratio and uses O(n2) queries. To the best of our knowledge, there is no deterministic algorithm for the constraint previously. The last algorithm can be adapted to attain a 0.432 ratio for single knapsack constraint using O(n4) queries. Previously, the best deterministic algorithm attains a 0.316−ϵ ratio and uses Õ(n3) queries [2]. © 2025 Elsevier B.V.
Keyword ：
Combinatorial optimization Combinatorial optimization Expectation maximization algorithm Expectation maximization algorithm Steepest descent method Steepest descent method
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Wan, Zongqi , Zhang, Jialin , Sun, Xiaoming et al. Efficient deterministic algorithms for maximizing symmetric submodular functions [J]. | Theoretical Computer Science , 2025 , 1046 . |
| MLA | Wan, Zongqi et al. "Efficient deterministic algorithms for maximizing symmetric submodular functions" . | Theoretical Computer Science 1046 (2025) . |
| APA | Wan, Zongqi , Zhang, Jialin , Sun, Xiaoming , Zhang, Zhijie . Efficient deterministic algorithms for maximizing symmetric submodular functions . | Theoretical Computer Science , 2025 , 1046 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
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 algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization.In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic 0.283 - ������(1) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio. For the linear packing constraints with large widths, we provide a deterministic 1/6 - ������ approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints.
Keyword ：
Derandomization Derandomization Deterministic algorithms Deterministic algorithms Multiplicative updates Multiplicative updates Submodular maximization Submodular maximization Twin greedy Twin greedy
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Sun, Xiaoming , Zhang, Jialin , Zhang, Shuo et al. Improved deterministic algorithms for non-monotone submodular maximization [J]. | THEORETICAL COMPUTER SCIENCE , 2023 , 984 . |
| MLA | Sun, Xiaoming et al. "Improved deterministic algorithms for non-monotone submodular maximization" . | THEORETICAL COMPUTER SCIENCE 984 (2023) . |
| APA | Sun, Xiaoming , Zhang, Jialin , Zhang, Shuo , Zhang, Zhijie . Improved deterministic algorithms for non-monotone submodular maximization . | THEORETICAL COMPUTER SCIENCE , 2023 , 984 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
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 horizon T suffer Omega(root T) regret. In this paper, we study MAB and SLB with quantum reward oracles and propose quantum algorithms for both models with O(poly(log T)) regrets, exponentially improving the dependence in terms of T. To the best of our knowledge, this is the first provable quantum speedup for regrets of bandit problems and in general exploitation in reinforcement learning. Compared to previous literature on quantum exploration algorithms for MAB and reinforcement learning, our quantum input model is simpler and only assumes quantum oracles for each individual arm.
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Wan, Zongqi , Zhang, Zhijie , Li, Tongyang et al. Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets [J]. | THIRTY-SEVENTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 37 NO 8 , 2023 : 10087-10094 . |
| MLA | Wan, Zongqi et al. "Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets" . | THIRTY-SEVENTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 37 NO 8 (2023) : 10087-10094 . |
| APA | Wan, Zongqi , Zhang, Zhijie , Li, Tongyang , Zhang, Jialin , Sun, Xiaoming . Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets . | THIRTY-SEVENTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 37 NO 8 , 2023 , 10087-10094 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Export
| Results： |
Selected to |
| Format： |
