8
votes
Accepted
Is it NP-hard to find an order on a set of strings so that the concatenation is a given string?
The problem is NP-hard already for $\Sigma = \{a, b\}$. (Of course, it is in PTIME if $|\Sigma| = 1$.) The reduction is from distinct-input 3-partition which is strongly NP-hard, i.e., intractable ...
- 8,896
7
votes
Accepted
Testing whether letters can be scheduled to achieve a word in a regular language
The problem is NP-hard for $L = A^*$ where $A$ is the finite language containing the following words:
$x111$, $x000$,
$y100$, $y010$, $y001$,
$00c11$, $01c10$, $10c01$, and $11c00$
The reduction is ...
- 2,758
6
votes
Who are active researchers in the scheduling theory?
It could be useful to look at the list of participants of recent Dagstuhl seminars on scheduling
http://www.dagstuhl.de/program/calendar/partlist/?semnr=13111
http://www.dagstuhl.de/program/calendar/...
- 1,978
5
votes
Who are active researchers in the scheduling theory?
Kirk Pruhs, Cliff Stein, Kamesh Munagala, Nikhil Bansal, Sungjin Im, Ben Moseley.
- 6,979
4
votes
Accepted
Complexity of Finding Optimal Synergistic Set Packings
This is an instance of the standard network flow problem called "Project Selection", and hence can be solved efficiently (even in practice). See (what's currently) Section 24.6 of Jeff Erickson's ...
- 1,429
3
votes
Accepted
The "electricity packing" problem
Here is an elaboration of my comment. From what I can understand, the OPs problem can be cast as the solution of a large implicit linear program. Given the $n$ numbers $d_1,d_2,\ldots,d_n$ let $\...
- 6,979
2
votes
Accepted
Color shifting in a bipartite graph
The precoloring extension problem is the following:
Input: a number $k$ and a graph $G$ some of whose edges are labeled with labels in $\{1, 2, \ldots, k\}$.
Decision: is it possible to color the ...
- 2,758
2
votes
Testing whether letters can be scheduled to achieve a word in a regular language
@MikhailRudoy was the first to show NP-hardness, but Louis and I had a different idea, which I thought I could outline here since it works somewhat differently.
We reduce directly from CNF-SAT, the
...
- 8,896
2
votes
Accepted
Scheduling to maximize idle time
Here's a paper that considers a more general variant of the problem (multiple machines, job dependent demands etc.):
Rohit Khandekar, Baruch Schieber, Hadas Shachnai, Tami Tamir.
Real-time ...
- 1,026
1
vote
Generalized assignment problem with overall budget
The problem is NP-hard, by reduction from the the knapsack problem. ($B$ represents the maximum weight capacity of the knapsack, and for each item, add a new pair of task and worker with cost equal ...
- 11.7k
1
vote
Solving Grouped Weighted Job Scheduling with Release Times and Deadlines on a Single Machine with Multiple Availability Intervals
Your problem can be formulated as an instance of the weighted interval scheduling problem (WISP), which is a well-studied problem in the literature. In WISP, we are given a set of jobs with release ...
- 13.9k
Only top scored, non community-wiki answers of a minimum length are eligible