# 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

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 ...

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 ...

8

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. ...

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 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} +...

7

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 ...

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

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

$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 ...

6

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 ...

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 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 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 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 + ... 4 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 ... 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 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 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<|...

4

Your problem is equivalent to asking whether there is some linear combination of row vectors from your $\mathbb R^{m\times n}$ matrix that has all coefficients positive and sums to a vector in which (a) every element is $\ge 0$ and (b) at least one element is $> 0$. (Notice that the order of the operations doesn't matter: Running them in some order might ...

4

For $i=1,\dots,N$, and $r \in \{S,R,B\}$ define $OPT[i,r]$ as the maximum profit that can be obtained by robbing a suitable subset of the first $i$ houses with the following constraints: If $x=S$ (as in Skip) then house $i$ must not be robbed. If $x=R$ then house $i$ must be Robbed while house $i+1$ will not be robbed (to avoid a case distinction later we ...

3

As O(2^n) says adding one item will double computation time, giving the fact that one day equals 2^16 seconds, you more or less answered the question yourself. A method solving a problem with 20 items in 1 second will will solve a problem with 20 + 16 = 36 items in a day. Wow, downvote for the right answer, that's nice! So let us elaborate on this: ...

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

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

The question "is there a subset that sums up to $t$?" has a YES/NO answer. In general, we shouldn't expect an algorithm to do more than it is asked to, so to speak. However, it is rather common that when an algorithm answers YES, it can also naturally give you a certificate that proves it. Moreover, when this happens, you typically get a one valid solution. (...

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

This problem can be solved in polynomial time using linear programming, and this is actually true for any partial order $(S,\le)$. By the way, we can prove by induction that for any finite partial order set $(S,\le)$, there exists a finite set $S'\subseteq\mathbb{N}$ and a bijection $f:S\rightarrow S'$, such that for all $s_1,s_2\in S, s_1\le s_2 \... 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 ...

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