violate
发表于 2025-3-26 23:14:39
A Weighted , ,-Free ,-Factor Algorithm for Bipartite Graphs no complete bipartite graph .. as a subgraph. When . = 2, this problem amounts to the minimum-weight square-free 2-factor problem in a bipartite graph, which is NP-hard. We propose, however, a strongly polynomial algorithm for a certain case where the weight vector is vertex-induced on any subgraph
exigent
发表于 2025-3-27 01:40:03
http://reply.papertrans.cn/47/4683/468262/468262_32.png
画布
发表于 2025-3-27 08:39:50
A Polynomial Algorithm for Weighted Abstract Flow In 1974 Hoffman pointed out that Ford and Fulkerson’s original proof was quite abstract, and applied to a wide range of flow problems. In this abstract model we have capacitated elements, and linearly ordered subsets of elements called paths. When two paths share an element (“cross”), then there mu
讲个故事逗他
发表于 2025-3-27 09:53:50
http://reply.papertrans.cn/47/4683/468262/468262_34.png
陈旧
发表于 2025-3-27 14:58:54
Binary Positive Semidefinite Matrices and Associated Integer Polytopestation. We then move on to consider the associated integer polytopes. Several important and well-known integer polytopes — the cut, boolean quadric, multicut and clique partitioning polytopes — are shown to arise as projections of binary psd polytopes. Finally, we present various valid inequalities
Reverie
发表于 2025-3-27 21:32:34
Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalitiesen added. We show that the integrality gap for such SDPs remains 2 − .(1) as long as .. This extends successive results by Kleinberg-Goemans, Charikar and Hatami et al. which analyzed integrality gaps of the standard . SDP relaxation as well as for SDPs tightened using triangle and pentagonal inequa
前奏曲
发表于 2025-3-27 22:38:42
Tight Bounds for Permutation Flow Shop Schedulingproblem, it is also required that each machine processes the set of all jobs in the . order. Formally, given . jobs along with their processing times on each machine, the goal is to compute a single permutation of the jobs .:[.]→[.], that minimizes the maximum job completion time (makespan) of the s
忧伤
发表于 2025-3-28 05:04:22
The Stochastic Machine Replenishment Problemy. The problem models the scheduling of processor repairs in a multiprocessor system in which one repair can be made at a time and the goal is to maximize system utilization. We analyze the performance of a natural greedy index policy for this problem. We first show that this policy is a 2 approxima
最高点
发表于 2025-3-28 09:29:10
A Polynomial Time Approximation Scheme for the Square Packing Problem a polynomial time approximation scheme for this problem, that for any value .> 0 finds and packs a subset .′ ⊆ . of profit at least (1 − .) ., where . is the profit of an optimum solution. This settles the approximability of the problem and improves on the previously best approximation ratio of 5/4
browbeat
发表于 2025-3-28 11:32:48
http://reply.papertrans.cn/47/4683/468262/468262_40.png