Skip to main content
Share Your Experience: Take the 2024 Developer Survey
9 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 ...
a3nm's user avatar
  • 9,409
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 ...
Mikhail Rudoy's user avatar
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 ...
Andrew Morgan's user avatar
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 $\...
Chandra Chekuri's user avatar
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 ...
Mikhail Rudoy's user avatar
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 ...
a3nm's user avatar
  • 9,409
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 ...
Thomas Kalinowski's user avatar
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 ...
D.W.'s user avatar
  • 12.1k
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 ...
domotorp's user avatar
  • 14k

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