1
$\begingroup$

I have a set of $K$ keywords. Each of this keywords can have a set of bids from $1\$,\ldots, N\$$. For each bid for a keyword, it will get a specific amount of clicks and a specific cost. Clicks and Cost are monotonic in bids. Now, the problem is:


Select a bid for each of the keyword such that overall clicks across the keywords are maximized such that the cost is still within a given budget $B$. Let $\text{Clicks}(W_i)$ and $\text{Cost}(W_i)$ denote the clicks and cost on the keyword $i$. Then (informally) the problem is to select a value of bid for each keyword such that \begin{align}\max\sum_{i=1}^{K}&\text{Clicks}(W_i) \\s.t.&~~\sum_{i=1}^{K}\text{Cost}(W_i)\leq B\end{align} Is this a type of knapsack problem? Are there any known heuristic in the literature.


Following is not important for the question (and thus can be skipped), but is for the curious ones to know how I am solving this currently.

Let $S_{ij}$ denote the cost for using bid $j$ for keyword $i$ and let $C_{ij}$ be the clicks for the same. Let $x_{ij}$ be the indicator variable for using bid $j$ for keyword $i$. Then among variables $x_{i1},\dots,x_{iN}$ only one can be non-zero (i.e. $x_{ij}=1$) whereas the rest is zero (since only one bid can chosen for keyword).

Thus, the whole problem can be formulated mathematically as

\begin{align}\max_{x_{ij}}~&\sum_{i=1}^{K}\sum_{j=1}^{N}x_{ij}C_{ij} \\s.t.~~\sum_{i=1}^{K}\sum_{j=1}^{N}&x_{ij}S_{ij}\leq B\\\sum_{j=1}^{N}x_{ij}=1&~~\forall i\in \{1,\dots,K\}~~,~~x_{ij}\in\{0,1\}\end{align}

Last, two constraints ensure they are indicator variables and only one bid is chosen for a given keyword. Solving this should solve the original problem.

$\endgroup$
1
$\begingroup$

Yes, it is called a multiple-choice knapsack problem. It can be solved in time $O(N B)$ by dynamic programming. The state of the dynamic program is given by a pair $(i, b)$ and the associated value is the maximum value (clicks) you can get with keywords from $1$ to $i$ with a budget at most $b$.

Source: S. Martello, P. Toth. Knapsack Problems. Wiley, 1990.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.