All Questions
Tagged with exp-time-algorithms big-picture
2 questions
3
votes
1
answer
139
views
Consequences of faster parameterized integer programming
Integer programming in $k$ variables can be done in $k^{O(k)}$ time and $O(k^c)$ space.
Is there any consequence if it can be done in $k^{O(k^\alpha)}$ time and $O(k^c)$ space for some $\alpha\in(0,1)...
- 13.3k
3
votes
3
answers
2k
views
Pseudo-polynomial time algorithms
Consider the following algorithm:
Given a natural number as input, say $N$, the algorithm runs a loop (in which the algorithm does $O(1)$ time operations) $N$ times. Now, by definition of time ...
- 1,364