Re: CACF invites you to the Project CHARGE 2008 Advocacy In (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Education - 教育学

Re: CACF invites you to the Project CHARGE 2008 Advocacy In (转载)

Re: CACF invites you to the Project CHARGE 2008 Advocacy In (转载)# Education - 教育学

g*u2008-08-02 07:08

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.
请问有没有已知的近似解法？谢谢！

s*g2008-08-02 07:08

2 楼

【以下文字转载自 Notice 讨论区】
发信人: deliver (自动发信系统), 信区:
标题: smugmug 封 sheji 在 TeX 版
发信站: BBS 未名空间站自动发信系统 (Fri Jun 24 11:52:54 2011)
【此篇文章是由自动发信系统所张贴】
由于 sheji 在 TeX 版的滥发广告行为，
被暂时取消在本版的发文权力 14 天。
版主:smugmug
Fri Jun 24 11:52:44 2011

L*k2008-08-02 07:08

3 楼

【以下文字转载自 NewYork 讨论区】
发信人: LXJSmonk (NYC_和尚), 信区: NewYork
标题: Re: CACF invites you to the Project CHARGE 2008 Advocacy Inst
发信站: BBS 未名空间站 (Sat Aug 2 17:18:02 2008)
The Coalition for Asian American Children and Families （CACF）
Through this advocacy training participants will:
1.Increase their understanding of effective advocacy skills and
strategies
2.Learn how to be more effective in hearings, press conferences, and
meetings with decision makers
Friday, August 8, 2008
10 am - 3 pm
Communit

c*t2008-08-02 07:08

4 楼

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*g2008-08-02 07:08

5 楼

整数线性规划，研究了好几十年了吧，有近似解法的。最简单的就是当作一般线性规划
解，然后对结果进行舍入。

【在 g*****u 的大作中提到】

g*u2008-08-02 07:08

6 楼

我就是从knapsack problem想到这个的。不一样的，knapsack是求最大值，这个求最小
值，knapsack的2-approximation algorithm不能用。其他knapsack的近似解法没看过。

【在 c*****t 的大作中提到】

: google 0-1 knapsack problem.

g*u2008-08-02 07:08

7 楼

你说rounding a fractional solution么？我也相信已经有人解过这个问题了，不过网
上找不到。你能给出个解法和作者么？我需要做个reference。

g*u2008-08-02 07:08

8 楼

我又想了一下，这个问题的optimal fractional solution就是按密度从小到大排队，
然后从头选一直选到满足size>=B的条件。最后一个选的可能是fractional的或者正好
。但是这样怎么round to a p-approximate integer solution呢？同样，用primal-
dual方法也不容易得出结论。
如果你知道，能不能写出具体算法和证明,或者出处？

【在 g*****u 的大作中提到】

: 你说rounding a fractional solution么？我也相信已经有人解过这个问题了，不过网
: 上找不到。你能给出个解法和作者么？我需要做个reference。

w*g2008-08-02 07:08

9 楼

这个我不是很在行。rounding technique也是随便想的，给不出reference。但是你这个
问题其实就是knapsack problem。假设所有物品的重量的总和为A，先解重量小于等于A
-B的
knapsack problem。把knapsack problem的解从所有物品中抛掉，剩下的就是你的问题
的解。

过。

【在 g*****u 的大作中提到】

: 我就是从knapsack problem想到这个的。不一样的，knapsack是求最大值，这个求最小
: 值，knapsack的2-approximation algorithm不能用。其他knapsack的近似解法没看过。

c*t2008-08-02 07:08

10 楼

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 的大作中提到】

g*u2008-08-02 07:08

11 楼

谢谢，和我以前想的一样。不过你有没有觉得，你说的这个knapsack problem的近似解
，比如它的approximation ration是2，但是，原来问题的解其实并没有bounded.
我已经想出一个算法了，不过不是常数级bounded。不过还是谢谢大家！

这个
于A

【在 w***g 的大作中提到】

: 这个我不是很在行。rounding technique也是随便想的，给不出reference。但是你这个
: 问题其实就是knapsack problem。假设所有物品的重量的总和为A，先解重量小于等于A
: -B的
: knapsack problem。把knapsack problem的解从所有物品中抛掉，剩下的就是你的问题
: 的解。
:
: 过。