Timeline for Approximate Subset Sum with negative numbers

9 events

when toggle format	what		by	license	comment
May 26, 2016 at 10:25	vote	accept	Harry
Nov 23, 2015 at 15:05	comment	added	SamM		I address this in my answer. Short answer is that $C \neq 0$ is not sufficient. You can get some bound on the error, but it's almost definitely not what you want.
Nov 23, 2015 at 14:31	comment	added	Harry		I see what are you saying. I will try to reform: approx-SS: Input: $A=\{a_i\mid a\in \mathbb{Z}\}$ possible negative, target $C\neq 0$, parameter $0\leq \epsilon \leq 1$. Question: Exists $A'\subseteq A$ such that $C\leq \sum_{a\in A'}a\leq (1+\epsilon)C$. What I ask is: Does this problem have an FPTAS? or does the FPTAS for the original all-positive SS remains a FPTAS for this? or can I transform it to an all-positive instance (with the reduction) and still get the error ratio I want?
Nov 18, 2015 at 19:46	history	edited	SamM	CC BY-SA 3.0	edited body
Nov 18, 2015 at 12:16	history	edited	SamM	CC BY-SA 3.0	added 70 characters in body
Nov 18, 2015 at 10:23	history	edited	SamM	CC BY-SA 3.0	added 25 characters in body
Nov 18, 2015 at 9:58	history	edited	SamM	CC BY-SA 3.0	added 100 characters in body
Nov 18, 2015 at 9:46	history	edited	SamM	CC BY-SA 3.0	deleted 20 characters in body
Nov 18, 2015 at 9:41	history	answered	SamM	CC BY-SA 3.0