g*****u
发帖数: 298 | 1 【 以下文字转载自 Computation 讨论区 】
发信人: grasssu (没有昵称), 信区: Computation
标 题: 请问一个基本的minimization problem有没有近似解法？
发信站: BBS 未名空间站 (Tue May 20 04:38:00 2008)
a set of objects (i from 1 to m), each has:
vi: the value of object i;
si: size of object i.
求选取a subset that can minimize the total value, subject to the condition
that total size greater than or equal to B.
请问有没有已知的近似解法？谢谢！ |
c*****t
发帖数: 1879 | 2 google 0-1 knapsack problem.
【在 g*****u 的大作中提到】
: 【 以下文字转载自 Computation 讨论区 】
: 发信人: grasssu (没有昵称), 信区: Computation
: 标 题: 请问一个基本的minimization problem有没有近似解法？
: 发信站: BBS 未名空间站 (Tue May 20 04:38:00 2008)
: a set of objects (i from 1 to m), each has:
: vi: the value of object i;
: si: size of object i.
: 求选取a subset that can minimize the total value, subject to the condition
: that total size greater than or equal to B.
: 请问有没有已知的近似解法？谢谢！
|
w***g
发帖数: 5958 | 3 整数线性规划，研究了好几十年了吧，有近似解法的。最简单的就是当作一般线性规划
解，然后对结果进行舍入。
【在 g*****u 的大作中提到】
: 【 以下文字转载自 Computation 讨论区 】
: 发信人: grasssu (没有昵称), 信区: Computation
: 标 题: 请问一个基本的minimization problem有没有近似解法？
: 发信站: BBS 未名空间站 (Tue May 20 04:38:00 2008)
: a set of objects (i from 1 to m), each has:
: vi: the value of object i;
: si: size of object i.
: 求选取a subset that can minimize the total value, subject to the condition
: that total size greater than or equal to B.
: 请问有没有已知的近似解法？谢谢！
|
g*****u
发帖数: 298 | 4 我就是从knapsack problem想到这个的。不一样的，knapsack是求最大值，这个求最小
值，knapsack的2-approximation algorithm不能用。其他knapsack的近似解法没看过。
【在 c*****t 的大作中提到】
: google 0-1 knapsack problem.
|
g*****u
发帖数: 298 | 5 你说rounding a fractional solution么？我也相信已经有人解过这个问题了，不过网
上找不到。你能给出个解法和作者么？我需要做个reference。 |
g*****u
发帖数: 298 | 6 我又想了一下，这个问题的optimal fractional solution就是按密度从小到大排队，
然后从头选一直选到满足size>=B的条件。最后一个选的可能是fractional的或者正好
。但是这样怎么round to a p-approximate integer solution呢？同样，用primal-
dual方法也不容易得出结论。
如果你知道，能不能写出具体算法和证明,或者出处？
【在 g*****u 的大作中提到】
: 你说rounding a fractional solution么？我也相信已经有人解过这个问题了，不过网
: 上找不到。你能给出个解法和作者么？我需要做个reference。
|
w***g
发帖数: 5958 | 7 这个我不是很在行。rounding technique也是随便想的，给不出reference。但是你这个
问题其实就是knapsack problem。假设所有物品的重量的总和为A，先解重量小于等于A
-B的
knapsack problem。把knapsack problem的解从所有物品中抛掉，剩下的就是你的问题
的解。
过。
【在 g*****u 的大作中提到】
: 我就是从knapsack problem想到这个的。不一样的，knapsack是求最大值，这个求最小
: 值，knapsack的2-approximation algorithm不能用。其他knapsack的近似解法没看过。
|
c*****t
发帖数: 1879 | 8 In the question:
求选取a subset that can minimize the total value, subject to the condition
that total size greater than or equal to B.
So basically, 0-1 knapsack would be finding the largest total size
for a given total value. If this size is greater than B, we are done.
过。
【在 g*****u 的大作中提到】
: 我就是从knapsack problem想到这个的。不一样的，knapsack是求最大值，这个求最小
: 值，knapsack的2-approximation algorithm不能用。其他knapsack的近似解法没看过。
|
g*****u
发帖数: 298 | 9 谢谢，和我以前想的一样。不过你有没有觉得，你说的这个knapsack problem的近似解
，比如它的approximation ration是2，但是，原来问题的解其实并没有bounded.
我已经想出一个算法了，不过不是常数级bounded。不过还是谢谢大家！
这个
于A
【在 w***g 的大作中提到】
: 这个我不是很在行。rounding technique也是随便想的，给不出reference。但是你这个
: 问题其实就是knapsack problem。假设所有物品的重量的总和为A，先解重量小于等于A
: -B的
: knapsack problem。把knapsack problem的解从所有物品中抛掉，剩下的就是你的问题
: 的解。
:
: 过。
|
