Share Your Experience: Take the 2024 Developer Survey

# Tag Info

Accepted

### Selling blocks of time slots

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 ...
• 1,183
Accepted

### How does the problem of "Scheduling to Minimize Lateness" exhibit optimal substructure?

Let us refine the "definition" of the optimal substructure property given in CLRS into two definitions. A problem exhibits strongly optimal substructure if every optimal solution to the ...
• 39k
Accepted

### Correctness proof for greedy algorithm based on ratio

The strategy to prove your ratio greedy algorithm is what I called "unimprovable solution by exchange of elements". Instead of proving that an algorithm produces the optimal solution, this strategy ...
• 39k
Accepted

### Response time of scheduling a DAG where each vertex is a task

Found it! This problem is NP-complete when the goal is to minimize total execution time. The scheduling problem (P1) is the following. We are given (1) a set $S = \{J_1 , \ldots , J_n\}$ of jobs, (2) ...
• 4,511

### DP for Weighted Interval Scheduling: why is sorting by finish time necessary?

Simple answer No, we cannot sort start time in ascending order to get a reasonable dynamic programming algorithm. A counterexample As illustrated above, we are given four jobs aligned in order of ...
• 652

When you compute the topological ordering, you usually select one node with no predecessor and remove it from the graph. Instead you can scan the whole list of vertices and select all source vertices ...
• 176
Accepted

### Disk scheduling algorithm - SCAN and C-SCAN

Here are the examples of various disk scheduling algorithms. Yes you are correct in both the case. The author here has made mistake. For SCAN: The answer should be 236. For C-SCAN: The answer should ...
• 146

### Selling blocks of time slots

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. ...
• 5,479
Accepted

### A specific version of a job scheduling problem

This scheduling problem is called non-preemptive job shop scheduling. The classic reference is Edward G Coffman, Jr, and Peter J Denning: Operating Systems Theory, Prentice-Hall, 1973. Job-shop ...
• 17.8k

### Interval Scheduling Problem with Three Resources

The greedy scheduling with a first fit resource selection is actually not correct. Consider the case where the intervals are: ${ (1, 3) , (2, 5) , (6, 7) , (4, 8) }$, for simplicity assume we only ...

### Designing a scheduling algorithm

Since a customer must either be assigned all the requested hours or none at all, this problem is $NP$-complete. This can be seen by reduction from Exact Cover. A polynomial algorithm is unlikely to ...
• 13.3k
Accepted

### Does an algorithm exist for scheduling jobs on two processors?

The algorithms for $n$ processors will do the job just fine for the 2-processor case. In this context, $n$ does not refer to the number of tasks to be scheduled, which probably caused the confusion ...
• 2,787
Accepted

### Algorithm to enumerate all complete schedulings of finals tests?

You're asking to enumerate all maximum matchings in a bipartite graph. Unfortunately that problem is #P-complete, so there is unlikely to be any efficient algorithm that works on arbitrary size ...
• 161k
Accepted

### Hardness of a scheduling/assignment problem

The problem is NP-hard, at least for a particular simplified configuration. Assume that each $m_l$ is effectively infinite - we can scan a particular libraries' books all on the day we get access. ...
• 13.6k

### Maximum interval scheduling - Circular Variation

Yes. What we need to do is, basically, running the $O(n^2)$ algorithm provided in the question, but without unnecessary intervals and redundant steps. Here is the gist of an $O(n\log n)$ algorithm. ...
• 39k
Accepted

### Order List of Sets so Adjacent Sets are Disjoint

You are asking two questions. I will only answer the first. What you are looking for is a Hamiltonian path in the Kneser graph $K(n,2)$. When $n = 5$, this is the Petersen graph, which contains a ...
• 277k

### Topological sort of minimum costs to finish interdependent tasks

This problem is basically to find the longest path in a directed acyclic graph (DAG). Let $cost[t]$ be the number of days it takes to do task $t$. Let $m[t]$ be the minimum number of days to finish ...
• 39k
Accepted

### Topological sort of minimum costs to finish interdependent tasks

I am assuming here that you are allowed to start tasks in parallel if there is no dependency between them, otherwise I think that no matter what order you do, the total time needed to finish the ...
• 2,745

### What is the average turnaround time?

In textbooks, the solution given is 6+8+13+20+21= 68/5 = 13.6 This is because the textbooks (including Operating System Concepts 8e by Silberschatz,Gagne,Gelvin) define turnaround time as the time ...

### How to choose waiting process in a preemptive priority-based scheduler

“Preemptive priority” is a property of a scheduler, it is not a complete specification. Under preemptive priority scheduling, you choose the waiting process that has the highest priority. If there are ...
Accepted

### Who was the first to define Flow Shop / Job Shop problem?

Coffman and Demming's famous Operating Systems Theory, 1973, section on Job Shop and Flow Shop problems (pp. 123-128) cites Conway, Maxwell, and Miller, 1967 as "a comprehensive treatment" ...
• 17.8k

### Scheduling N variable-time interdependent tasks across M workers

This can been seen as a variation of the job shop problem where you want to find the policy that yields the minimum makespan (time taken for all machines to process all jobs); as well as a variation ...
• 829

### Minimum sum of distance from entrance gate

I will try to give a solution. Tell me if I am mistaking anywhere. First observation : When we have equal number of chairs and persons the solution is trivial.Ask all the people from 1st gate to fill ...
Accepted

### What is the best Approximation algorithm to schedule a task graph?

You get a $2-\frac1m$-approximation (where $m$ is the number of machines), by greedily scheduling tasks as they become available, and this is essentially the best we can do at the moment. Improving ...
Accepted

### Lower bound on competitive ratio of $m$-machine scheduling

Consider first the sequence $m \times 1$. If the algorithm schedules all the 1's in different machines, then its competitive ratio is 1. Otherwise, its competitive ratio is at least 2 (since the ...
• 277k

### Work-stealing: where and how many to steal

I did some experiments about this myself a while back so I hope I can still give some insight. This approach is called "Idempotent Work Stealing" and was defined (to the best of my knowledge) here. It ...
• 211

### What are some examples of problems whose deterministic versions are easy, but become hard when injecting some uncertainty?

Linear Quadratic Regulation is a standard control-theoretic problem that is easy when deterministic. The problem is to minimize a quadratic cost while steering a linear system: https://en.wikipedia....
• 81

### Find a schedule with lowest total penalty

This problem is called "minimization of total weighted flow time". It is very hard, especially when jobs cannot be preempted by the processor. Even when jobs can be preempted, it is NP-hard, so you ...
• 3,302