DCOS集群资源分配是np-hard
DCOS cluster resource allocation is np-hard
DCOS 文档中指出
"Deciding where to run processes to best utilize cluster resources is
hard, NP-hard in-fact."
我不否认这听起来是对的，但是有什么证据吗？
资源的最佳利用是 bin packaging problem 的变体：
In the bin packing problem, objects of different volumes must be
packed into a finite number of bins or containers each of volume V in
a way that minimizes the number of bins used. In computational
complexity theory, it is a combinatorial NP-hard problem. The decision
problem (deciding if objects will fit into a specified number of bins)
is NP-complete.
我们有 n 维 space，其中每个维对应一种资源类型。每个要安排的任务都有由所需资源定义的特定数量。此外，任务可以具有略微改变原始任务的约束，但我们可以将此约束视为额外的离散维度。任务是以最小化闲置资源的方式安排任务，从而防止碎片化。
例如Marathon使用首次拟合算法，它是近似算法但还不错：
This is a very straightforward greedy approximation algorithm. The algorithm processes the items in arbitrary order. For each item, it attempts to place the item in the first bin that can accommodate the item. If no bin is found, it opens a new bin and puts the item within the new bin.
It is rather simple to show this algorithm achieves an approximation factor of 2, that is, the number of bins used by this algorithm is no more than twice the optimal number of bins.
DCOS 文档中指出
"Deciding where to run processes to best utilize cluster resources is hard, NP-hard in-fact."
我不否认这听起来是对的，但是有什么证据吗？
资源的最佳利用是 bin packaging problem 的变体：
In the bin packing problem, objects of different volumes must be packed into a finite number of bins or containers each of volume V in a way that minimizes the number of bins used. In computational complexity theory, it is a combinatorial NP-hard problem. The decision problem (deciding if objects will fit into a specified number of bins) is NP-complete.
我们有 n 维 space，其中每个维对应一种资源类型。每个要安排的任务都有由所需资源定义的特定数量。此外，任务可以具有略微改变原始任务的约束，但我们可以将此约束视为额外的离散维度。任务是以最小化闲置资源的方式安排任务，从而防止碎片化。
例如Marathon使用首次拟合算法，它是近似算法但还不错：
This is a very straightforward greedy approximation algorithm. The algorithm processes the items in arbitrary order. For each item, it attempts to place the item in the first bin that can accommodate the item. If no bin is found, it opens a new bin and puts the item within the new bin.
It is rather simple to show this algorithm achieves an approximation factor of 2, that is, the number of bins used by this algorithm is no more than twice the optimal number of bins.