Let $v_i, s_i$ be the value and size of item $i$, let $\rho \in \mathbb{R}$, n be the maximum number of items. Then we add items based on $\frac{v_i}{s_i^{\rho}}$ in decreasing order. I was trying to understand a proof in a paper, but I get stuck at some points. The utility function $u_{\rho}$ is the value of items selected by the greedy algorithm for an given input x under a parameter setting $\rho$.
*Fix some instance x. Suppose Algorithm $A_{\rho_1}$ produces a different solution on x than $A_{\rho_2}$ for $\rho_1 < \rho_2$. Consider the first point they differ, $A_{\rho_1}$ adds item i while $A_{\rho_2}$ adds item j. Then it must be he case that $\frac{v_i}{s_i^{\rho_1}} - \frac{v_j}{s_j^{\rho_1}} \geq 0, \frac{v_i}{s_i^{\rho_2}} - \frac{v_j}{s_j^{\rho_2}} \leq 0$. Consider the function $f(\rho) = \frac{v_i}{s_i^{\rho}} - \frac{v_j}{s_j^{\rho}}$. This is a continuous function and there must exist some value $c \in [\rho_1, \rho_2]$ such that $f(\rho) = 0$.
For any given pair of items $i, j$, there is at most one value of $\rho > 0$ such that $f(\rho) = 0$ and there are at most $\binom{n}{2}$ critical values c. *By the argument above, the algorithm will produce the same solution for all $\rho$ within the interval between any two consecutive critical values.*
My main confusion comes from the bolded lines. How do the proof conclued there is at most one value $\rho > 0$ such that $f(\rho) = 0$ and how to conclude the algorithm is invariant between two consecutive critical point values?
Here is the link for the paper https://arxiv.org/pdf/2011.07177.pdf. It was written by Maria-Florina Balcan. I was trying to understand Theorem 2.4 in this paper. I believe this paper is open-sourced, so it contains more details for the proof.

  • $\begingroup$ Welcome to CS.SE! Can you edit your post to give a citation to the paper (title, authors, where published, and a link to a freely available copy if possible), and clearly indicate which parts of your question are copied or quotations from the paper? $\endgroup$
    – D.W.
    Dec 29 '21 at 22:17
  • $\begingroup$ I think the paper says "there must exist some value", it does not say at most one. For any value $\rho$ in that interval, the knapsack items are sorted the same way so the algorithm (described in the paper) will produce the same solution. $\endgroup$
    – TickaJules
    Dec 30 '21 at 0:37
  • $\begingroup$ Yes, the paper prove there must exist some value, and then in the third paragraph, it mentions there is at most one parameter setting such that the function achieves 0. $\endgroup$
    – Sophie
    Dec 30 '21 at 1:14
  • $\begingroup$ I think the function $f(\rho)$ is monotone, which would imply it crosses 0 just once in the interval. $\endgroup$
    – TickaJules
    Dec 30 '21 at 1:22
  • $\begingroup$ I agree with this idea, but how does this implies the function still produces the same solutions for the next iterations? We are only analyzing the case where the two algorithms produce different solutions for the first time, how about the proceeding solutions? $\endgroup$
    – Sophie
    Dec 30 '21 at 1:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.