# Questions tagged [pseudo-polynomial]

The tag has no usage guidance.

26 questions
Filter by
Sorted by
Tagged with
42 views

### A variant of the knapsack problem

Consider the following variant for the knapsack problem: the input are disjoint sets of items $T_1, T_2, ..., T_m$ (each contains items of a different type). Every item $i$ has a value of $v_i$ and a ...
33 views

### Do pseudo-polynomial algorithms for NPC-problems scale in practice?

Given for example the NP-complete (NPC) Knapsack-problem, we know that there exists pseudo-polynomial algorithms that run in $O(n*w)$, where $W$ is pseudopolynomial. Are those algorithms useful to ...
83 views

### pseudo-polynomial reduction from 3-Partition to Partition

A problem $\Pi'$ is pseudo-polynomially reducible to the problem $\Pi$ ($\Pi' \leq_{pp} \Pi$) if, for any instance $I'$ of $\Pi'$, an instance $I$ of $Π$ can be constructed in pseudo-polynomially ...
70 views

### How can I develop a pseudo-polynomial time algorithm for a non-integer problem?

I have an scheduling probelm with a set of jobs $J$, with a ''non-integer'' parameter $\beta_j$, i.e. the parameter is a real number and $\beta_j \leqslant 0.5, \exists j \in J$. Since the problem ...
574 views

808 views

### Why addition algorithm is not pseudo- polynomial?

There is something I don't understand. In the Subset Sum problem, in the Dynamic Programming solution, because of binary representation of the sum T, we say it is pseudo-polynomial in run time; we ...
73 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 ...
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 ...