Query：
学者姓名：张智杰
Refining：
Year
Type
Indexed by
Source
Complex
Co-
Language
Clean All
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： |
