The first nontrivial lower bound of the worst-case approximation ratio for the maxcut problem was achieved via the dual Cheeger problem,whose optimal value is referred to as the dual Cheeger constant h^(+),and later i...The first nontrivial lower bound of the worst-case approximation ratio for the maxcut problem was achieved via the dual Cheeger problem,whose optimal value is referred to as the dual Cheeger constant h^(+),and later improved through its modification h^(+).However,the dual Cheeger problem and its modification themselves are relatively unexplored,especially the lack of effective approximate algorithms.To this end,we first derive equivalent spectral formulations of h^(+)and h^(+)within the framework of the nonlinear spectral theory of signless 1-Laplacian,present their interactions with the Laplacian matrix and 1-Laplacians,and then use them to develop an inverse power algorithm that leverages the local linearity of the objective functions involved.We prove that the inverse power algorithm monotonically converges to a ternary-valued eigenvector,and provide the approximate values of h^(+)and h^(+)on the G-set for the first time.The recursive spectral cut algorithm for the maxcut problem can be enhanced by integrating it into the inverse power algorithms,leading to significantly improved approximate values on the G-set.Finally,we show that the lower bound of the worst-case approximation ratio for the maxcut problem within the recursive spectral cut framework cannot be improved beyond 0.769.展开更多
We propose a simple iterative(SI)algorithm for the maxcut problem through fully using an equivalent continuous formulation.It does not need rounding at all and has advantages that all subproblems have explicit analyti...We propose a simple iterative(SI)algorithm for the maxcut problem through fully using an equivalent continuous formulation.It does not need rounding at all and has advantages that all subproblems have explicit analytic solutions,the cut values are monotonically updated and the iteration points converge to a local optima in finite steps via an appropriate subgradient selection.Numerical experiments on G-set demonstrate the performance.In particular,the ratios between the best cut values achieved by SI and those by some advanced combinatorial algorithms in[Ann.Oper.Res.,248(2017),365-403]are at least 0.986 and can be further improved to at least 0.997 by a preliminary attempt to break out of local optima.展开更多
In scenarios where a large amount of data needs to be learned,incremental learning can make full use of old knowledge,signif-icantly reduce the computational cost of the overall learning process,and maintain high perf...In scenarios where a large amount of data needs to be learned,incremental learning can make full use of old knowledge,signif-icantly reduce the computational cost of the overall learning process,and maintain high performance.In this paper,taking the MaxCut problem as our example,we introduce the idea of incremental learning into quantum computing,and propose a Quantum Proactive Incremental Learning algorithm(QPIL).Instead of a one-off training of quantum circuit,QPIL contains a multi-phase training on gradually-increased subgraphs of all vertices,proactively reducing large-scale problems to smaller ones to solve in steps,providing an efficient solution for MaxCut.Specifically,some vertices and corresponding edges are randomly selected for training to obtain optimized parameters of the quantum circuit at first.Then,in each incremental phase,the remaining vertices and corresponding edges are gradually added and the parameters obtained from the previous phase are reused in the parameter initialization of the current phase.We perform experiments on 120 different small-scale graphs,and it shows that QPIL performs superior to prevalent quantum and classical baselines in terms of approximation ratio(AR),time cost,anti-forgetting,and solv-ing stability.In particular,QPIL’s AR surpasses 20%of mainstream quantum baselines,and the time cost is less than 1/5 of them.The idea of QPIL is expected to inspire efficient and high-quality solutions in large-scale MaxCut and other combinatorial optimization problems.展开更多
基金supported by the National Key R&D Program of China(No.2022YFA 1005102)National Natural Science Foundation of China(Grant Nos.12401443,12325112 and 12288101).
文摘The first nontrivial lower bound of the worst-case approximation ratio for the maxcut problem was achieved via the dual Cheeger problem,whose optimal value is referred to as the dual Cheeger constant h^(+),and later improved through its modification h^(+).However,the dual Cheeger problem and its modification themselves are relatively unexplored,especially the lack of effective approximate algorithms.To this end,we first derive equivalent spectral formulations of h^(+)and h^(+)within the framework of the nonlinear spectral theory of signless 1-Laplacian,present their interactions with the Laplacian matrix and 1-Laplacians,and then use them to develop an inverse power algorithm that leverages the local linearity of the objective functions involved.We prove that the inverse power algorithm monotonically converges to a ternary-valued eigenvector,and provide the approximate values of h^(+)and h^(+)on the G-set for the first time.The recursive spectral cut algorithm for the maxcut problem can be enhanced by integrating it into the inverse power algorithms,leading to significantly improved approximate values on the G-set.Finally,we show that the lower bound of the worst-case approximation ratio for the maxcut problem within the recursive spectral cut framework cannot be improved beyond 0.769.
基金supported by the National Key R&D Program of China(Grant Nos.2020AAA0105200,2022YFA1005102)the National Natural Science Foundation of China(Grant Nos.12325112,12288101,11822102)the China Postdoctoral Science Foundation(Grant No.BX201700009).
文摘We propose a simple iterative(SI)algorithm for the maxcut problem through fully using an equivalent continuous formulation.It does not need rounding at all and has advantages that all subproblems have explicit analytic solutions,the cut values are monotonically updated and the iteration points converge to a local optima in finite steps via an appropriate subgradient selection.Numerical experiments on G-set demonstrate the performance.In particular,the ratios between the best cut values achieved by SI and those by some advanced combinatorial algorithms in[Ann.Oper.Res.,248(2017),365-403]are at least 0.986 and can be further improved to at least 0.997 by a preliminary attempt to break out of local optima.
基金supported by the National Natural Science Foundation of China(Grant Nos.62272048,61976056,and 62371069)BUPT Excellent Ph.D.Students Foundation(Grant No.CX20241055)。
文摘In scenarios where a large amount of data needs to be learned,incremental learning can make full use of old knowledge,signif-icantly reduce the computational cost of the overall learning process,and maintain high performance.In this paper,taking the MaxCut problem as our example,we introduce the idea of incremental learning into quantum computing,and propose a Quantum Proactive Incremental Learning algorithm(QPIL).Instead of a one-off training of quantum circuit,QPIL contains a multi-phase training on gradually-increased subgraphs of all vertices,proactively reducing large-scale problems to smaller ones to solve in steps,providing an efficient solution for MaxCut.Specifically,some vertices and corresponding edges are randomly selected for training to obtain optimized parameters of the quantum circuit at first.Then,in each incremental phase,the remaining vertices and corresponding edges are gradually added and the parameters obtained from the previous phase are reused in the parameter initialization of the current phase.We perform experiments on 120 different small-scale graphs,and it shows that QPIL performs superior to prevalent quantum and classical baselines in terms of approximation ratio(AR),time cost,anti-forgetting,and solv-ing stability.In particular,QPIL’s AR surpasses 20%of mainstream quantum baselines,and the time cost is less than 1/5 of them.The idea of QPIL is expected to inspire efficient and high-quality solutions in large-scale MaxCut and other combinatorial optimization problems.
