无动于衷
发表于 2025-3-23 12:26:37
Lecture Notes in Computer Sciencehttp://image.papertrans.cn/i/image/468255.jpg
opalescence
发表于 2025-3-23 13:59:22
A Faster Scaling Algorithm for Minimizing Submodular Functions,chrijver. The IFF algorithm employs a scaling scheme for submodular functions, whereas Schrijver’s algorithm exploits distance labeling. This paper combines these two techniques to yield a faster combinatorial algorithm for submodular function minimization. The resulting algorithm improves over the
轻快带来危险
发表于 2025-3-23 21:37:44
,A Generalization of Edmonds’ Matching and Matroid Intersection Algorithms,roved that this problem is solvable in polynomial time via the ellipsoid method. We present a polynomial-time combinatorial algorithm for its unweighted version that generalizes the known combinatorial algorithms for the cardinality matching problem and the matroid intersection problem.
神圣在玷污
发表于 2025-3-24 02:06:38
http://reply.papertrans.cn/47/4683/468255/468255_14.png
Neonatal
发表于 2025-3-24 04:47:58
The Quickest Multicommodity Flow Problem,this method makes available the whole algorithmic toolbox developed for static flows, its main and often fatal drawback is the enormous size of the time-expanded network. In particular, this approach usually does not lead to efficient algorithms with running time polynomial in the input size since t
大门在汇总
发表于 2025-3-24 07:16:58
A New Min-Cut Max-Flow Ratio for Multicommodity Flows,tio, capacity of a cut is scaled by the demand that has to cross the cut. In the denominator, the maximum concurrent flow value is used. Our new bound is proportional to log(.*) where .* is the cardinality of the minimal vertex cover of the demand graph.
deficiency
发表于 2025-3-24 10:52:01
Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems,s for the MAX 2-SAT and MAX DI-CUT problems. These approximation algorithms start by solving semidefinite programming relaxations of these problems. They then . the solution obtained, as suggested by Feige and Goemans. Finally, they round the rotated vectors using random hyperplanes chosen according
地壳
发表于 2025-3-24 16:40:34
Finding the Exact Integrality Gap for Small Traveling Salesman Problems,hich seems promising for finding improved solutions for the STSP is the study of a linear relaxation of this problem called the Subtour Elimination Problem (SEP). A well known conjecture in combinatorial optimization says that the integrality gap of the SEP is 4/3 in the metric case. Currently the b
Dedication
发表于 2025-3-24 19:55:58
http://reply.papertrans.cn/47/4683/468255/468255_19.png
包租车船
发表于 2025-3-25 02:33:55
http://reply.papertrans.cn/47/4683/468255/468255_20.png