The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
51 views

An algorithm for making 2 carts meet [closed]

Say I have 2 carts on an infinite railroad, each cart is initially under a lamp. There are only 2 lamps, and they are at a fixed location, hence they don't change their location. The distance between ...
4
votes
1answer
572 views

Do I understand pseudo polynomial time correctly?

The running time of knapsack is $O(n*W)$, but we always specify that this is only pseudo-polynomial. I was wondering if somebody could tell me if I understand the notion of pseudo-polynomial time ...
5
votes
2answers
223 views

Weak and strong completeness

What does a pseudo-polynomial algorithm tell us about the problem it solves? I don't see how running time improves if the algorithm is exponential in the input length and polynomial in the input ...