刺耳
发表于 2025-3-25 05:01:14
,A First Order Method for Linear Programming Parameterized by Circuit Imbalance,e constraint matrix is totally unimodular, we obtain polynomial-time algorithms, whereas the convergence guarantees for approaches based on primal-dual formulations may have arbitrarily slow convergence rates for this class. Our approach is based on a fast gradient method due to Necoara, Nesterov, a
aggravate
发表于 2025-3-25 09:10:18
http://reply.papertrans.cn/47/4683/468257/468257_22.png
屈尊
发表于 2025-3-25 13:47:13
http://reply.papertrans.cn/47/4683/468257/468257_23.png
丰满中国
发表于 2025-3-25 18:50:49
,Adaptivity Gaps in Two-Sided Assortment Optimization,nts one by one is exactly 1/2. Finally, we observe that the worst policies are those who simultaneously show assortments to all the agents, in fact, we show that the adaptivity gap with respect to one-sided policies can be arbitrarily small. These results showcase the benefit of each class of polici
喊叫
发表于 2025-3-25 22:15:03
http://reply.papertrans.cn/47/4683/468257/468257_25.png
fulcrum
发表于 2025-3-26 02:52:42
Integer Programming and Combinatorial Optimization25th International C
Instrumental
发表于 2025-3-26 05:29:22
,Sparsity and Integrality Gap Transference Bounds for Integer Programs, study the additive integrality gap of the integer linear programs ., where . is a polyhedron in the standard form determined by an integer . matrix . and an integer vector .. The main result of the paper gives an upper bound for the integrality gap that drops exponentially in the size of support of
榨取
发表于 2025-3-26 12:26:30
,Separating , from the Supplier Version, ratio 2.613 holds for the more general . where an additional set . is given with the restriction ., the best known hardness for these two versions are . and . respectively, using the same reduction from .. We prove the following two results separating them..Our upper bound and lower bound are deriv
Jingoism
发表于 2025-3-26 16:13:21
,A Better-Than-1.6-Approximation for Prize-Collecting TSP,ties. The quality of a solution is then measured by adding the length of the tour and the sum of all penalties of vertices that are not visited. We present a polynomial-time approximation algorithm with an approximation guarantee slightly below 1.6, where the guarantee is with respect to the natural
construct
发表于 2025-3-26 18:26:23
http://reply.papertrans.cn/47/4683/468257/468257_30.png