随机算法 \ 高级算法 (Fall 2016)/Problem Set 2

每道题目的解答都要有完整的解题过程。中英文不限。

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.