27
$\begingroup$

Given $n$ time slots that $k$ people want to buy. Person $i$ has a value $h(i,j)\geq 0$ for each time slot $j$. Each person can only buy one consecutive block of time slots, which could be empty.

Is there a polynomial-time algorithm to compute the maximum value the seller can achieve?

Without the consecutiveness constraint, we can give each time slot to the person who values it most. Also, if we fix the order of the time slots of the $k$ people, then dynamic programming can be used to solve for the maximum value of the first $0\le i \le k$ people buying the first $0\le j \le n$ time slots.

$\endgroup$
9
+50
$\begingroup$

Given a 3CNF with clauses $\phi_1,\ldots,\phi_k$ on variables $x_1,\ldots,x_n$. Suppose both $x_i$ and $\overline{x_i}$ appear in the formula for at most $k_i$ times respectively.

We design a colored DAG $G$ whose vertices consists of three parts:

  • "Assignment" vertices $v_i(j)$ and $\bar{v}_i(j)$, $1\leq i\leq n$, $1\leq j\leq k_i$. Color $v_i(j)$ with the "color" $x_i(j)$, and $\bar{v}_i(j)$ with $\overline{x_i}(j)$.
  • "Clause" vertices $w_{i'}(j')$, $1\leq i'\leq k$, $j'=1,2,3$. Color $w_{i'}(j')$ with the color $x_i(j)$ (or $\overline{x_i}(j)$) if $\overline{x_i}$ (or $x_i$, resp.) is the $j'$-th literal of clause $\phi_{i'}$, and it's the $j$-th clause containing this literal.
  • "Cut" vertices $s=s_0,s_1,\ldots,s_n, s_{n+1},\ldots s_{n+k}=t$. Color them with distinct colors different from above.

The edges include:

  • $s_{i-1}v_i(1)$, $v_i(j)v_i(j+1)$, $v_i(k_i)s_i$;
  • $s_{i-1}\bar{v}_i(1)$, $\bar{v}_i(j)\bar{v}_i(j+1)$, $\bar{v}_i(k_i)s_i$;
  • and $s_{n+i'-1}w_{i'}(j')$, $w_{i'}(j')s_{n+i'}$.

For instance, from the 3CNF $(x_1 \vee x_2 \vee \overline{x_3})\wedge(x_1 \vee \overline{x_2}\vee x_3)$ the following graph is constructed (The edge directions are from left to right). enter image description here

Now it is not hard to see that the original 3CNF is satisfiable if and only if there is a $s$-$t$ path with different vertex colors in $G$.

(By the way, it is a by-product that the existsence of $s$-$t$ path with different vertex colors in colored DAG is $\textsf{NP-hard}$. I didn't find many literatures about this problem in computational perspective. If you know, please comment!)

So what is the relation between $G$ and OP's problem? Intuitively what we are going to do is to design a matrix $h$, so that each color is mapped to a row (which is a person), and the edges are mapped to consecutive columns (time slots). Therefore a maximum scheduling, which is basically going from left to right in the matrix, corresponds to an $s$-$t$ path.

Our matrix $h$ have $2n+1+\sum_i 2k_i+k$ columns, with indices starting from $0$. In the following constrcution $X$ an $Y$ are two values satisfy $1\ll X\ll Y$. The ratios $X/1, Y/X$ can be large powers of $k$ and $n$. Let $K_i=2i+2\sum_{j=1}^i k_i$.

  • For each $s_i$, $0\leq i\leq n$, let $h(s_i,K_i)=h(s_i,K_i-k_i-1)=h(s_i,K_i+k_{i+1}+1)=Y$ (if the coordinate exists, same below).
  • For each $x_i(j)$, let $h(x_i(j),K_{i-1}+j)=X$; For each $\overline{x_i}(j)$, let $h(\overline{x_i}(j),K_{i-1}+k_i+1+j)=X$.
  • For each $\phi_{i'}$, $1\leq i'\leq k$ and a literal $x$ in the clause $\phi_{i'}$, let $h(x,K_n+i')=1$.
  • All the other entries are 0.

For example, for the above example graph the corresponding matrix is enter image description here

Now we claim: the original 3CNF is satisfiable if and only if the maximum value is $(2n+1)Y+\sum_i k_iX+k$.

Consider the scheduling achieving the maximum value. Since there are exactly $(2n+1)$ columns in $h$ containing $Y$, they should all be covered. For the column $K_i+k_i+1$ which has two choices of $Y$, suppose the scheduling assigns it to $s_i$. Since column $K_i$ must be assigned to $s_i$, by the consecutiveness we have to lose the columns $K_i+1$ to $K_i+k_i$. Same things happen if the scheduling assign the column $K_i+k_i+1$ to $s_{i+1}$.

Therefore, in order to have the value $\sum_i k_iX$, we must select all the rest available $X$'s in the matrix, which corresponds to an assignment on variables. So the rest value of $k$ is achievable if and only if the assignment satisfy every clause.

As a conclusion, deciding the maximum value of a legal scheduling is in $\textsf{NP-hard}$. Maybe that's why all our previous attempts to find an algorithm failed.

$\endgroup$
  • $\begingroup$ But, in the example matrix, if i pick $\overline{x_1}$ $\overline{x_2}$ and ${x_3}$ i still can get to the objective. What i´m doing wrong? Also the $X$ in $\overline{x_1}(1)$ should be one column to the right and the $X$ in $\overline{x_1}(2)$ should be one column to the left $\endgroup$ – rotia Nov 23 '16 at 23:47
  • $\begingroup$ @rotia Yes, and that means on the left you must pick $x_1,x_2,\overline{x_3}$ to have $4X$. So that corresponds to a satisfying assignment $x_1=x_2=1,x_3=0$. $\endgroup$ – Willard Zhan Nov 24 '16 at 1:27
  • $\begingroup$ Can you clarify what "Suppose $k_i$ larger one in the two numbers of appearances of literals $x_i$ and $\overline{x_i}$." means? What is the number of appearance of a literal? Is that something about where it appears in the clauses/formula, or is it how many times it appears in the formula? Is $k_i$ a literal or a number? $\endgroup$ – D.W. Nov 24 '16 at 2:32
  • $\begingroup$ @D.W. $k_i$ is a number. My expression was indeed quite not clear; I've edited it. $\endgroup$ – Willard Zhan Nov 24 '16 at 2:53
  • $\begingroup$ @WillardZhan Yes. But if i pick those variables i can get to a value that is bigger than the one in the formula. For instance, i set $Y = 60$ and $X = 7$, according to the formula i should get only to 450 points (assuming $k$ is the number of clauses). But, by choosing $x_1,x_2,\overline{x_3}$ i can get to 452 points by picking the four ones at the right $\endgroup$ – rotia Nov 24 '16 at 11:10
3
$\begingroup$

This solution has problems and will be deleted soon; see templatetypedef's comment.

You can solve this in polynomial time using minimum-cost flow. In the following, all edges have unit capacity.

  • Create a source vertex $s$, and a target vertex $t$. We will send $k$ units of flow from $s$ to $t$.
  • Create $n+1$ vertices $v_0, \dots, v_n$ to represent the time points between slots, and a directed edge $v_jv_{j+1}$ for each $0 \le j < n$ with cost 0.
  • For each person $i$, create the following:
    • A sub-source vertex $s_i$ and a sub-sink vertex $t_i$.
    • For every $0 \le j < n$, an edge from $s_i$ to $v_j$ having cost $\Sigma_{k=1}^j{h(i,k)}$ (which we take to be 0 if $j=0$).
    • For every $1 \le j \le n$, an edge from $v_j$ to $t_i$ having cost $-\Sigma_{k=1}^j{h(i,k)}$.
    • An edge $ss_i$ with cost 0.
    • An edge $t_it$ with cost 0.

A minimum-cost flow in this network will have total cost equal to the negative of the best possible profit. (This cost will be negative, but that's not a problem.) There is an optimal integral solution in which every person $i$ has a single edge leaving $s_i$ with a flow of 1 and a single edge arriving at $t_i$ with a flow of 1, and all other edges incident on either $s_i$ or $t_i$ have 0 flow. Let these flow-1 edges for person $i$ be $s_iv_j$ and $v_kt_i$: then $k \ge j$, since the only paths among $v$-vertices are those that increase the subscript. If $k = j$, then person $i$ is allocated no time slots; otherwise, person $i$ is allocated the block of time slots $j+1, \dots, k$.

Intuitively, each person "gets" 1 unit of flow from $s$ and chooses a start time (edge) and end time (edge); these start and end edges are the only edges with nonzero cost in the network, and we can represent the value of a block $j+1, \dots, k$ as the difference of two prefix sums. The unit capacities on the edges between the $v$-vertices act to prevent 2 people from using the same time slot.

Interestingly, this formulation will work even if the values $h(i, j)$ may be negative.

$\endgroup$
  • 3
    $\begingroup$ Might this fail if some person $i$ takes a route from their source to another person's sink and vice-versa? $\endgroup$ – templatetypedef Nov 22 '16 at 16:28
  • $\begingroup$ @templatetypedef: I believe you're right; I'll delete this answer shortly. What about this construction instead: We have the same vertices and edges as before, but now we try to "thread" a single unit of flow through a "pipeline" of people (ordered by increasing $i$ value) by deleting all edges $ss_i$ except for $ss_1$ and all edges $t_it$ except for $t_kt$, and adding an edge $t_is_{i+1}$ with huge negative cost $-M$ for each $1 \le i < k$. The $-M$s will force the single unit of flow to visit all $k-1$ of these "pipeline" edges in any optimal solution. $\endgroup$ – j_random_hacker Nov 22 '16 at 17:29
  • $\begingroup$ @j_random_hacker then you are forcing an ordering of the $k$ people. $\endgroup$ – Chao Xu Nov 22 '16 at 17:37
  • $\begingroup$ @ChaoXu: I don't think so: in any assignment of blocks to people, the assignment can be listed in increasing order by person. (Notice that nothing forbids a person $i' > i$ being assigned a block ending at $j' < j$, where $j$ is the first block assigned to person $i$.) But I have a feeling that a close relative of the problem that affected my first attempt also affects this one... $\endgroup$ – j_random_hacker Nov 22 '16 at 17:39
  • $\begingroup$ @j_random_hacker The cost of $s_iv_j$ would require that $s_i$ to be the $i$th person in the optimal solution. $\endgroup$ – Chao Xu Nov 22 '16 at 17:45

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.