# Tag Info

9

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 DAG $G$ whose vertices consists of three parts: "Assignment" vertices $v_i(j)$ and $\bar{v}_i(j)$, $1\leq i\leq n$, $1\leq j\leq k_i$. Color $v_i(j)$ with the ...

8

The graph of overlapping jobs is an interval graph. Interval graphs are perfect graphs. So what you are trying to do is find a maximum weight independent set (i.e., no two overlap) in a perfect graph. This can be solved in polynomial time. The algorithm is given in "Polynomial Algorithms for Perfect Graphs", by M. Grötschel, L. Lovász, and A. Schrijver. ...

6

Greedy algorithm can't help in that case. And it couldn't be compared with both fractional or 0-1 knapsack problems. The first could be resolved by greedy algorithm in O(n) and the second is NP. The problem you have could be brute-forced in O(2^n). But you could optimize it using dynamic programming. 1) Sort intervals by start time. 2) Initialize int[] ...

5

One could implement this in O(nlogn) Steps: Sort the intervals based on end time define p(i) for each interval, giving the biggest end point which is smaller than the start point of i-th interval. Use binary search to obtain nlogn define d[i] = max(w(i) + d[p(i)], d[i-1]). initialize d = 0 The result will be in d[n] n- the number of intervals. ...

5

This seems to be exercise 9 from Kleinberg's Algorithm Design, chapter six. I'll report how i tried to solve it. Let's define $OPT(i)$ as the maximum amount of work from day $1$ to day $i$, with $i \leq n$ For every $i$, there can be a reboot in any previous day $1\leq j < i$. If it was on day $j$, than you processed $\sum_{k=j+1}^i \min\left\{s_{k-j}, ... 4 For the Round-Robin Scheduler the quantum time is to ensure that each process has a share to the CPU and we don't have starvation problems. It's known for being fair, such that each process shares the CPU equality. Quantum time is it's the amount of time spent on each process in the CPU until we context switch to the next process in the ready queue. For ... 4 This has always troubled me too. The problem is with the origins of the English word and the difference between ordinal numbers ("first", "second", "third", ...) and cardinal numbers (the numbers you use to count things). In schedulers we use the word priority in the sense of: the right to take precedence or to proceed before others It came into ... 4 This sounds very much like a Hamilton path problem. If you set the edge weights all to$1$and the deadline of the vertices all to$|V| - 1$, then each vertex can only be visited once, since there is not enough time to visit one twice before the deadline runs out. Finding a Hamilton path on the other hand is NP-hard. Thus, your problem is NP-hard as well. 4 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 and remove them at once, only then you update the degree of the remaining vertices. The groups of vertices you remove together represent tasks that can be ... 3 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 exist. Starting with biggest job first might be a reasonable heuristic for many cases, but there are no performance guarantees. 3 This is more a question of English than computer science. For almost any regular verb (and "schedule" is a perfect example), the [verb]er is the thing that does the [verb]ing. The scheduler is the software that schedules. 3 The shortest-task-first heuristic is a 1/2-approximation algorithm. For a tight example, image that a compatible set$\{T_i\mid 1\leq i\leq m\}$sorted by their finish time and the other shorter tasks$Y_i$,$1\leq i\leq m/2$, such that$Y_i$overlaps with$T_{2i-1}$and$T_{2i}$for each$i$. The shortest-first heuristic finds$m/2$tasks while the optimal ... 3 Simple Google search reveals a thesis from 2010 that defines and proves the complexity of scheduling university courses as NP-Complete. See Fig. 42 towards the end. Lovelace, April L. "On the complexity of scheduling university courses." (2010). There is also a technical report dating back to 1995 that does the same thing: Cooper, Tim B., and Jeffrey H. ... 3 When an I/O is started, it will typically have an I/O request structure associated with it that includes items like the process ID that the I/O belonged to. When the I/O completes the device driver will typically fork into an OS level I/O subsystem in the OS which will queue the IO request packet notification to the process and move the process to a ... 3 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 have 2 resources. The greedy algorithm will assign intervals 1, 2, 3 to resources 1, 2, 1 respectively and will fail to assign a resource for the last interval. ... 3 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 scheduling is discussed in Section 3.7 and 3.8 (although they mainly focus on a restricted version of the problem called the flow shop problem where the$a_i$... 3 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. Create a source vertex$s$, and a target vertex$t$. We will send$k$units of flow from$s$to$t$. Create$n+1$vertices$v_0, \dots, v_n$to represent the ... 3 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 be 146+37=183.(Note: The head movement when its not servicing any requests is not counted.) Refer the link, it gives a clear concept of how the different kinds ... 3 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 when you looked for algorithms. Then, there is a great website for searching for scheduling problems, which you can access at http://www-desir.lip6.fr/~durrc/... 3 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 problem contains optimal solutions to subproblems. A problem exhibits weakly optimal substructure if there is at least one optimal solution to the problem contains ... 3 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 require you to show that every optimal solution that cannot be improved by an exchange of two or more elements must be or must be equivalent to the solution ... 3 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) a partial order$\prec$on$S$, (3) a weighting function$W$from$Sto the positive integers, giving the number of time units required by each job, and (4) a ... 3 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 ascending start time, each labeled with its wight. Though some computation, we havep_4=3$and$OPT(4)=1+OPT(3)$. By definition,$OPT(3)$equals to the optimal ... 3 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 graphs. There might be algorithms that work well enough for your situation, given the small numbers you're dealing with. For instance, a simple approach is to use ... 3 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. Let all$d_l = 1$- each library takes one day to get access to, meaning we get access to exactly$n$libraries. Now if$P_b = 1\$ the thing that maximizes our ...

2

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 that elapses between the submission and the termination of the process, which is the sum of arrival time, waiting time, execution time and time spent in device ...

2

This is actually a bin packing problem, rather than a scheduling problem. If I remember correctly (it's been a long time) bin packing is the dual of scheduling. In the most basic kind of bin packing problems each room would be available for exactly three hours, and the goal would be to minimize the total number of three-hour sessions you would consume. ...

2

Instead of putting x, put some very high cost values in those cells. Then the Hungarian algorithm avoids selecting those cells automatically (if that's possible).

2

I think you're not using the same terminology as the books and articles you're reading. Non-preemptive schedulers suffer from priority inversion, not convoy effects. Most scheduling disciplines (FIFO, SJF, LJF, Nearest-deadline-first, ...) can be reframed as highest priority first schedulers, where what changes from discipline to discipline is the ...

2

It depends on what you are trying to achieve, but generally i/o intensive jobs should receive a higher priority, and a small time quantum. I assume you are asking about some variety of multilevel feedback queuing. The idea behind multilevel feedback queue-based schedulers is to try to approximate shortest remaining time first scheduling, where you are ...

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