Timeline for Selling blocks of time slots
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 22, 2016 at 17:45 | comment | added | Chao Xu | @j_random_hacker The cost of $s_iv_j$ would require that $s_i$ to be the $i$th person in the optimal solution. | |
| Nov 22, 2016 at 17:39 | comment | added | j_random_hacker | @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... | |
| Nov 22, 2016 at 17:37 | comment | added | Chao Xu | @j_random_hacker then you are forcing an ordering of the $k$ people. | |
| Nov 22, 2016 at 17:30 | history | edited | j_random_hacker | CC BY-SA 3.0 |
Warn that there are problems.
|
| Nov 22, 2016 at 17:29 | comment | added | j_random_hacker | @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. | |
| Nov 22, 2016 at 16:28 | comment | added | templatetypedef | Might this fail if some person $i$ takes a route from their source to another person's sink and vice-versa? | |
| Nov 22, 2016 at 13:09 | history | answered | j_random_hacker | CC BY-SA 3.0 |