# Tag Info

12

When we say polynomial or exponential, we mean polynomial or exponential in some variable. $nW$ is polynomial in $n$ and $W$. However, we usually consider the running time of an algorithm as a function of the size of the input. This is where the argument about $\log W$ comes in. Ignoring the values of the items for the moment (and considering only their ...

9

Very nice question! You are twice right: Propagating the number of items in the knapsack does not lead to optimal solutions. One solution consists of adding a third dimension. This is rather simple but it is necessary to take some facts into account when doing so. Note however that it is not the only alternative In the following, I am assuming that you ...

9

Your problem is NP-complete, by reduction from Subset Sum (it is in NP since the fact that everything is non-negative bounds the coefficients of the solution sufficiently well). Given an instance $S = \{s_1,\ldots,s_n\}, T$ of Subset Sum (is there a subset of $S$ summing to $T$?), we construct an instance $v_1,\ldots,v_{2n},u$ of your problem as follows. For ...

8

The key to understanding a dynamic programing problem is understanding the recursive definition and this can be daunting. For this problem we start with n objects labeled 1 to n. We define $O(K,W)$ to be the optimal value for the first k items with a total weight W, we need to be able to define this in terms of subproblems now since without that, dynamic ...

7

The graph of overlapping jobs is an interval graph. Interval graphs are perfect graphs. So what you are trying to do is find a maximum weight independent set (i.e., no two overlap) in a perfect graph. This can be solved in polynomial time. The algorithm is given in "Polynomial Algorithms for Perfect Graphs", by M. Grötschel, L. Lovász, and A. Schrijver. ...

6

Greedy algorithm can't help in that case. And it couldn't be compared with both fractional or 0-1 knapsack problems. The first could be resolved by greedy algorithm in O(n) and the second is NP. The problem you have could be brute-forced in O(2^n). But you could optimize it using dynamic programming. 1) Sort intervals by start time. 2) Initialize int[] ...

6

Polynomial time means that the running time is bounded by a polynomial in the length of the input. The running time here is bounded by $nW$. $n$, the number of items, is surely less than the length of the input, so that part is fine. But $W$, the target weight, is a number that appears in the input, in binary. In $\ell$ bits, you can write a ...

6

The approximation ratio is always strictly larger than $1/2$. Let $p_1,\ldots,p_{k-1}$ be the values of the items picked by algorithm, and let $p_k$ be the value of the next item which would have been picked had it fit. Let $\alpha$ be the fraction of $p_k$ that does fit – so $\alpha < 1$. These lecture notes (Claim 2) show that  p_1 + \cdots + p_{k-1} +...

5

This is a common misconception many have. Subset sum, among others, is NP-complete only if the input is encoded in binary (or ternary etc). In unary encoding it's polynomial-time solvable by a simple dynamic programming approach. These problems are sometimes referred as weakly NP-complete. If you're not quite sure what I mean by unary encoding: Unary ...

5

One could implement this in O(nlogn) Steps: Sort the intervals based on end time define p(i) for each interval, giving the biggest end point which is smaller than the start point of i-th interval. Use binary search to obtain nlogn define d[i] = max(w(i) + d[p(i)], d[i-1]). initialize d = 0 The result will be in d[n] n- the number of intervals. ...

5

I'll just leave a broad hint. Suppose $H(1:n)=[h_1,h_2\ldots,h_n]$ is the list of houses. Suppose that we already know the set of houses to buy for the subarray $H(1:n-1)$. This solution either includes $h_{n-1}$ in its optimal list, or it doesn't. If it does include $h_{n-1}$, then we can't add $h_n$ to the list and we are done. If it doesn't include $h_{n-... 5 Dynamic programming One approach is to use dynamic programming. If you have$n$numbers ($n$rows in the file), and each number is in the range$1..m$, then the obvious dynamic programming algorithm has running time about$8mn$. For your parameter size, this might be adequate. In particular, let$A[1..n]$be an array of your$n$numbers. Define$T[x,i,j]...

5

$n$ is not part of the input, $n$ denotes the number of objects in the input. The input consists of the capacity of the knapsack, a list of objects, each with a value and weight. If there are $n$ objects in the instance then the size of the instance is at least $n$ since each object needs to be represented (with at least one bit). Therefore $n$ is ...

5

The problem you have given is similar to KNAPSACK as Yuval Filmus mentioned. KNAPSACK problem is defined as: maximize $\sum_{i=1}^n v_i x_i$ subject to $\sum_{i=1}^n w_i x_i \leq W$ and $x_i \in \{0,1\}.$ I assume the pair (0,0) is used so that you may not choose pairs for some of the $M_j$'s. Otherwise (0,0) pair is irrelevant in the problem. If this ...

5

You can formulate problems like this as an integer program and apply off-the-shelf tools to find (near) optimal solutions. The example is rendered something like this (the exact syntax depends on the tool). minimize 5*BX + 10*BZ + 4*CY + 6*CZ + 10*DX + 7*DYZ subject to BX + DX = 1 # project X is done once CY + DYZ = 1 # project Y is done once BZ + CZ + ...

5

There is no guarantee that the packing algorithm you suggested will lead to an optimal packing. Say you have two knapsacks of capacity 5, and objects of size 1, 2, 3 and 4. An optimal packing would be putting 1 and 4 into knapsack 1, and 2 and 3 into the other knapsack (switching the indexes on the knapsacks would also be another alternative solution and ...

4

(1) NP-complete only contains problems that can be answered by Yes or No, which are called decision problems. So FACTOR is not an NP-complete problem even your reduction is correct. In fact, if your reduction were correct, it proves that FACTOR is NP-hard. (2) If you want to prove the NP-hardness of FACTOR by reducing UKP (unbounded knapsack problem) to it, ...

4

You can't. Landau notation does not hold enough information. You don't know the constant factor(s). With only $O$, you don't have a lower bound. It's only a worst-case bound; different runs with the number of items can have wildly different runtimes. Such bounds only hold in the limit, that is even $\leq c \cdot 2^n$ may not hold for those $n$ you can ...

4

The input to 0/1 knapsack is a list of $n$ items each with a weight $w_i$ and value $v_i$ with knapsack size $W$ and maximum value $V$. Thus the input list has size $O(n (\log W + \log V))$. So $n \log n$ is polynomial in the input. The problem with the traditional dynamic programming solution of knapsack is not that it is exponential in $n$, but that it ...

4

You are on the right track. It turns out the original question can be solved by a greedy algorithm. (A full blown solution by dynamic programming as I tried a while ago is both an overkill on coding and short of performance.) Let us use the notation in the original question. $R$ is for the resistance capacity. $S$ is for the array of strengths. Let the ...

4

As you're aware, "polynomial time" means that there is a polynomial $p$ such that the running time on input $X$ is at most $p(|X|)$. An input to the knapsack problem consists of a list of $n$ weights, a list of $n$ values and a maximum weight $W$. Since each weight and each value must take at least one bit to write down, we know that $n<|... 3 I think mainly the techniques that are covered in that section (dynamic programming and greedy algorithms) are very important. There are several other properties. First of all, integral knapsack problem belongs to the famous class of problems called NP-complete (there is no known polynomial time algorithm for them), while the fractional knapsack is ... 3 Hint: Let$x$be the item of smallest weight (and so of highest value). Take any solution which doesn't contain$x$. If there is room for$x$, add it to the solution. Otherwise, remove some element and add$x$(why is that possible? does it necessarily improve the solution?). Conclude that the optimal solution always contains$x$. Apply this reasoning ... 3 Your problem is called 3D Bin Packing and is indeed an NP problem. Looking those key words on Google will yield many articles about more or less complex approximation algorithms that can help you solve this problem. 3 You may be interested in reading about total unimodularity. An ILP is solvable in polynomial time if the associated matrix is totally unimodular (sufficient but not necessary condition). This explains the tractability of assignment and maximum flow problems. I'm not aware of any "reason" why knapsack is pseudopolynomial time solvable. 3 Your assumption is wrong; the dynamic programming algorithm does not do that. It computes$m(n,W)$according to the recurrence$\qquad\displaystyle m(i,w) = \begin{cases} 0, &i=0 \lor w=0; \\ m(i-1,w), & w_i > w; \\ \max \{ m(i-1,w), m(i-1, w - w_i) + v_i \}, &w_i \leq w . \end{cases} $Here,$(w_1, v_1), \dots, (w_n, v_n)$... 3 Yes, this can be solved using a dynamic programming algorithm very similar to the standard dynamic programming algorithm for the knapsack problem. Basically, order the positions from 1 to 9. You're going to fill in a two-dimensional table$T$, where$T[i,s]$denotes the score of the highest-scoring team that fills in just the first$i$positions and has a ... 3 I have read that one needs$\lg ⁡W$to represent$W$so it is exponential-time. But, I don't understand, also one needs$\lg ⁡n$to represent$n$, no? This is a great question. You need to look at what the input actually is. The input consists of$n$items, each of which has a weight$w_i$and value$v_i$, plus the capacity$W\$ of your ...

3

It is common to assume without loss of generality that the maximum item weight is at most as large as the knapsack capacity. That is okay (in the context of complexity theory) because filtering out items that are too large to fit even alone is easily possible in a polynomial-time preprocessing step. If the sources do not mention that they are sloppy. And ...

Only top voted, non community-wiki answers of a minimum length are eligible