Post by Alon on Jun 20, 2017 14:37:41 GMT
We are required to find an example which demonstrates that the FPTAS algorithm is not monotone. I tried several directions. A natural attempt is to seek for an instance with w_1=W=1, w_2=...=w_k=1/(k-1), v_1>\sum_{j>1}
v_j, such that for some choice of \epsilon, due to rounding errors, v'_1<\sum_{j>1}
v'_j. This does not seem to work. Finally, I considered a scenario where there is one large bid with weight w_1=2/3, two medium bids with weights w_2=w_3=1/3 and two small bids with w_4=w_5=1/6. The first bidder would like to report a bid such that v_'1+v'_4+v'_5 > v'_2+v'_3. For some choice of v_1,\ldots, v_5 and \epsilon, the first bidder utilizes the rounding error, whereas the last two bidders have no rounding error. In order to help them, he slightly decreases its bid. Furthermore, the values v_2, v_3 are chosen such that after modifying v_1, their rounding error vanish.
While this solution works, I wonder if there if someone found a simpler construction.
Thanks:)
v_j, such that for some choice of \epsilon, due to rounding errors, v'_1<\sum_{j>1}
v'_j. This does not seem to work. Finally, I considered a scenario where there is one large bid with weight w_1=2/3, two medium bids with weights w_2=w_3=1/3 and two small bids with w_4=w_5=1/6. The first bidder would like to report a bid such that v_'1+v'_4+v'_5 > v'_2+v'_3. For some choice of v_1,\ldots, v_5 and \epsilon, the first bidder utilizes the rounding error, whereas the last two bidders have no rounding error. In order to help them, he slightly decreases its bid. Furthermore, the values v_2, v_3 are chosen such that after modifying v_1, their rounding error vanish.
While this solution works, I wonder if there if someone found a simpler construction.
Thanks:)
