Mixing
FPTAS definition
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
I read that a fully polynomial time approximation scheme (FPTAS) has time complexity polynomial in the input size and also polynomial in $1/epsilon$. However, this leaves some ambiguity.
For example, $T(n,1/epsilon)=min(n^1/epsilon,(1/epsilon)^n)$ is both polynomial in $n$ (when holding $1/epsilon$ constant) and polynomial in $1/epsilon$ (when holding $n$ constant). But $T$ is not polynomial in $n/epsilon$ or $(n+1/epsilon)$ because $sqrt x^sqrt x$ and $(x/2)^x/2$ aren't bounded by polynomials.
Does this mean an algorithm with running time $T$ isn't an FTPAS, and perhaps a better definition would be that it has to be polynomial in $n+1/epsilon$?
algorithms complexity-theory terminology
asked 2 days ago
Akababa
1184
add a comment |Â
up vote
3
down vote
favorite
I read that a fully polynomial time approximation scheme (FPTAS) has time complexity polynomial in the input size and also polynomial in $1/epsilon$. However, this leaves some ambiguity.
For example, $T(n,1/epsilon)=min(n^1/epsilon,(1/epsilon)^n)$ is both polynomial in $n$ (when holding $1/epsilon$ constant) and polynomial in $1/epsilon$ (when holding $n$ constant). But $T$ is not polynomial in $n/epsilon$ or $(n+1/epsilon)$ because $sqrt x^sqrt x$ and $(x/2)^x/2$ aren't bounded by polynomials.
Does this mean an algorithm with running time $T$ isn't an FTPAS, and perhaps a better definition would be that it has to be polynomial in $n+1/epsilon$?
algorithms complexity-theory terminology
asked 2 days ago
Akababa
1184
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I read that a fully polynomial time approximation scheme (FPTAS) has time complexity polynomial in the input size and also polynomial in $1/epsilon$. However, this leaves some ambiguity.
For example, $T(n,1/epsilon)=min(n^1/epsilon,(1/epsilon)^n)$ is both polynomial in $n$ (when holding $1/epsilon$ constant) and polynomial in $1/epsilon$ (when holding $n$ constant). But $T$ is not polynomial in $n/epsilon$ or $(n+1/epsilon)$ because $sqrt x^sqrt x$ and $(x/2)^x/2$ aren't bounded by polynomials.
Does this mean an algorithm with running time $T$ isn't an FTPAS, and perhaps a better definition would be that it has to be polynomial in $n+1/epsilon$?
algorithms complexity-theory terminology
asked 2 days ago
Akababa
1184
I read that a fully polynomial time approximation scheme (FPTAS) has time complexity polynomial in the input size and also polynomial in $1/epsilon$. However, this leaves some ambiguity.
For example, $T(n,1/epsilon)=min(n^1/epsilon,(1/epsilon)^n)$ is both polynomial in $n$ (when holding $1/epsilon$ constant) and polynomial in $1/epsilon$ (when holding $n$ constant). But $T$ is not polynomial in $n/epsilon$ or $(n+1/epsilon)$ because $sqrt x^sqrt x$ and $(x/2)^x/2$ aren't bounded by polynomials.
Does this mean an algorithm with running time $T$ isn't an FTPAS, and perhaps a better definition would be that it has to be polynomial in $n+1/epsilon$?
algorithms complexity-theory terminology
asked 2 days ago
Akababa
1184
asked 2 days ago
Akababa
1184
asked 2 days ago
Akababa
1184
asked 2 days ago
Akababa
1184
1184
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
The standard definition is incredibly ambiguous, since it is not clear what "polynomial in $n$ and in $1/epsilon$" means. Judging from examples, it means $O(n^C(1/epsilon)^D)$ for some constants $C,D$. Without loss of generality, $C=D$, and then we get the simpler definition $O((n/epsilon)^C)$.
answered 2 days ago
Yuval Filmus
179k12167327
Thanks for clarifying. Although might $O((n+1/epsilon)^C)$ be more precise because when $epsilon=n$ is very large, $n/epsilon=1$ but it should still take at least $O(n)$ to find a feasible solution?
– Akababa
2 days ago
The big O holds in the limit $ntoinfty$ and $epsilonto0$. We can assume that $epsilon < 1 < n$, say.
– Yuval Filmus
2 days ago
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
The standard definition is incredibly ambiguous, since it is not clear what "polynomial in $n$ and in $1/epsilon$" means. Judging from examples, it means $O(n^C(1/epsilon)^D)$ for some constants $C,D$. Without loss of generality, $C=D$, and then we get the simpler definition $O((n/epsilon)^C)$.
answered 2 days ago
Yuval Filmus
179k12167327
Thanks for clarifying. Although might $O((n+1/epsilon)^C)$ be more precise because when $epsilon=n$ is very large, $n/epsilon=1$ but it should still take at least $O(n)$ to find a feasible solution?
– Akababa
2 days ago
The big O holds in the limit $ntoinfty$ and $epsilonto0$. We can assume that $epsilon < 1 < n$, say.
– Yuval Filmus
2 days ago
add a comment |Â
up vote
2
down vote
accepted
The standard definition is incredibly ambiguous, since it is not clear what "polynomial in $n$ and in $1/epsilon$" means. Judging from examples, it means $O(n^C(1/epsilon)^D)$ for some constants $C,D$. Without loss of generality, $C=D$, and then we get the simpler definition $O((n/epsilon)^C)$.
answered 2 days ago
Yuval Filmus
179k12167327
Thanks for clarifying. Although might $O((n+1/epsilon)^C)$ be more precise because when $epsilon=n$ is very large, $n/epsilon=1$ but it should still take at least $O(n)$ to find a feasible solution?
– Akababa
2 days ago
The big O holds in the limit $ntoinfty$ and $epsilonto0$. We can assume that $epsilon < 1 < n$, say.
– Yuval Filmus
2 days ago
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
The standard definition is incredibly ambiguous, since it is not clear what "polynomial in $n$ and in $1/epsilon$" means. Judging from examples, it means $O(n^C(1/epsilon)^D)$ for some constants $C,D$. Without loss of generality, $C=D$, and then we get the simpler definition $O((n/epsilon)^C)$.
answered 2 days ago
Yuval Filmus
179k12167327
The standard definition is incredibly ambiguous, since it is not clear what "polynomial in $n$ and in $1/epsilon$" means. Judging from examples, it means $O(n^C(1/epsilon)^D)$ for some constants $C,D$. Without loss of generality, $C=D$, and then we get the simpler definition $O((n/epsilon)^C)$.
answered 2 days ago
Yuval Filmus
179k12167327
answered 2 days ago
Yuval Filmus
179k12167327
answered 2 days ago
Yuval Filmus
179k12167327
answered 2 days ago
Yuval Filmus
179k12167327
179k12167327
Thanks for clarifying. Although might $O((n+1/epsilon)^C)$ be more precise because when $epsilon=n$ is very large, $n/epsilon=1$ but it should still take at least $O(n)$ to find a feasible solution?
– Akababa
2 days ago
The big O holds in the limit $ntoinfty$ and $epsilonto0$. We can assume that $epsilon < 1 < n$, say.
– Yuval Filmus
2 days ago
add a comment |Â
Thanks for clarifying. Although might $O((n+1/epsilon)^C)$ be more precise because when $epsilon=n$ is very large, $n/epsilon=1$ but it should still take at least $O(n)$ to find a feasible solution?
– Akababa
2 days ago
The big O holds in the limit $ntoinfty$ and $epsilonto0$. We can assume that $epsilon < 1 < n$, say.
– Yuval Filmus
2 days ago
Thanks for clarifying. Although might $O((n+1/epsilon)^C)$ be more precise because when $epsilon=n$ is very large, $n/epsilon=1$ but it should still take at least $O(n)$ to find a feasible solution?
– Akababa
2 days ago
Thanks for clarifying. Although might $O((n+1/epsilon)^C)$ be more precise because when $epsilon=n$ is very large, $n/epsilon=1$ but it should still take at least $O(n)$ to find a feasible solution?
– Akababa
2 days ago
The big O holds in the limit $ntoinfty$ and $epsilonto0$. We can assume that $epsilon < 1 < n$, say.
– Yuval Filmus
2 days ago
The big O holds in the limit $ntoinfty$ and $epsilonto0$. We can assume that $epsilon < 1 < n$, say.
– Yuval Filmus
2 days ago
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f95988%2ffptas-definition%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password