随机算法 \ 高级算法 (Fall 2016)/Problem Set 2: Difference between revisions
Jump to navigation
Jump to search
imported>Etone Created page with "每道题目的解答都要有<font color="red" >完整的解题过程</font>。中英文不限。 == Problem 1== Consider the following optimization problem. *'''Instance''..." |
imported>Etone |
||
| Line 4: | Line 4: | ||
== Problem 1== | == Problem 1== | ||
Consider the following optimization problem. | Consider the following optimization problem. | ||
:'''Instance''': <math>n</math> positive integers <math>x_1<x_2<\cdots <x_n</math>. | |||
:Find two ''disjoint'' nonempty subsets <math>A,B\subset\{1,2,\ldots,n\}</math> with <math>\sum_{i\in A}x_i\ge \sum_{i\in B}x_i</math>, such that the ratio <math>\frac{\sum_{i\in A}x_i}{\sum_{i\in B}x_i}</math> is minimized. | |||
Give a pseudo-polynomial time algorithm for the problem, and then give an FPTAS for the problem based on the pseudo-polynomial time algorithm. | |||
Revision as of 13:24, 20 October 2016
每道题目的解答都要有完整的解题过程。中英文不限。
Problem 1
Consider the following optimization problem.
- Instance: [math]\displaystyle{ n }[/math] positive integers [math]\displaystyle{ x_1\lt x_2\lt \cdots \lt x_n }[/math].
- Find two disjoint nonempty subsets [math]\displaystyle{ A,B\subset\{1,2,\ldots,n\} }[/math] with [math]\displaystyle{ \sum_{i\in A}x_i\ge \sum_{i\in B}x_i }[/math], such that the ratio [math]\displaystyle{ \frac{\sum_{i\in A}x_i}{\sum_{i\in B}x_i} }[/math] is minimized.
Give a pseudo-polynomial time algorithm for the problem, and then give an FPTAS for the problem based on the pseudo-polynomial time algorithm.