The 2024 Developer Survey results are live! See the results

# Tag Info

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 ...
• 9,677
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,873
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
Accepted

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 $\... • 7,029 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,036 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 ... • 9,677 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 ... • 12.3k 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 ... • 14.1k 1 vote 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,873

Only top scored, non community-wiki answers of a minimum length are eligible