Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Interval_scheduling> ?p ?o }
Showing triples 1 to 41 of
41
with 100 triples per page.
- Interval_scheduling abstract "Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design. The problems consider a set of tasks. Each task is represented by an interval describing the time in which it needs to be executed. For instance, task A might run from 2:00 to 5:00, task B might run from 4:00 to 10:00 and task C might run from 9:00 to 11:00. A subset of intervals is compatible if no two intervals overlap. For example, the subset {A,C} is compatible, as is the subset {B}; but neither {A,B} nor {B,C} are compatible subsets, because the corresponding intervals within each subset overlap.The interval scheduling maximization problem (ISMP) is to find a largest compatible set - a set of non-overlapping intervals of maximum size. The goal here is to execute as many tasks as possible.In an upgraded version of the problem, the intervals are partitioned into groups. A subset of intervals is compatible if no two intervals overlap, and moreover, no two intervals belong to the same group (i.e. the subset contains at most a single representative interval of each group).The group interval scheduling decision problem (GISDP) is to decide whether there exists a compatible set in which all groups are represented. The goal here is to execute a single representative task from each group. GISDPk is a restricted version of GISDP in which the number of intervals in each group is at most k.The group interval scheduling maximization problem (GISMP) is to find a largest compatible set - a set of non-overlapping representatives of maximum size. The goal here is to execute a representative task from as many groups as possible. GISMPk is a restricted version of GISMP in which the number of intervals in each group is at most k. This problem is often called JISPk, where J stands for Job.GISMP is the most general problem; the other two problems can be seen as special cases of it: ISMP is the special case in which each task belongs to its own group (i.e. it is equal to GISMP1). GISDP is the problem of deciding whether the maximum is exactly equal to the number of groups.".
- Interval_scheduling thumbnail IntervalSelection.svg?width=300.
- Interval_scheduling wikiPageID "7570573".
- Interval_scheduling wikiPageLength "12505".
- Interval_scheduling wikiPageOutDegree "20".
- Interval_scheduling wikiPageRevisionID "679298623".
- Interval_scheduling wikiPageWikiLink 2-SAT.
- Interval_scheduling wikiPageWikiLink 2-satisfiability.
- Interval_scheduling wikiPageWikiLink APX.
- Interval_scheduling wikiPageWikiLink Algorithm.
- Interval_scheduling wikiPageWikiLink Boolean_satisfiability_problem.
- Interval_scheduling wikiPageWikiLink Category:Scheduling_algorithms.
- Interval_scheduling wikiPageWikiLink Charging_argument.
- Interval_scheduling wikiPageWikiLink Computer_science.
- Interval_scheduling wikiPageWikiLink Earliest_deadline_first_scheduling.
- Interval_scheduling wikiPageWikiLink Greedy_algorithm.
- Interval_scheduling wikiPageWikiLink Independent_set_(graph_theory).
- Interval_scheduling wikiPageWikiLink Intersection_graph.
- Interval_scheduling wikiPageWikiLink Job_stream.
- Interval_scheduling wikiPageWikiLink Linear_programming_relaxation.
- Interval_scheduling wikiPageWikiLink MaxSNP.
- Interval_scheduling wikiPageWikiLink Maximum_disjoint_set.
- Interval_scheduling wikiPageWikiLink NP-complete.
- Interval_scheduling wikiPageWikiLink NP-completeness.
- Interval_scheduling wikiPageWikiLink Scheduling_(computing).
- Interval_scheduling wikiPageWikiLink File:IntervalSelection.svg.
- Interval_scheduling wikiPageWikiLinkText "interval scheduling".
- Interval_scheduling hasPhotoCollection Interval_scheduling.
- Interval_scheduling wikiPageUsesTemplate Template:Reflist.
- Interval_scheduling subject Category:Scheduling_algorithms.
- Interval_scheduling hypernym Problems.
- Interval_scheduling type Disease.
- Interval_scheduling type Algorithm.
- Interval_scheduling comment "Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design. The problems consider a set of tasks. Each task is represented by an interval describing the time in which it needs to be executed. For instance, task A might run from 2:00 to 5:00, task B might run from 4:00 to 10:00 and task C might run from 9:00 to 11:00. A subset of intervals is compatible if no two intervals overlap.".
- Interval_scheduling label "Interval scheduling".
- Interval_scheduling sameAs m.0265mbd.
- Interval_scheduling sameAs Q17092629.
- Interval_scheduling sameAs Q17092629.
- Interval_scheduling wasDerivedFrom Interval_scheduling?oldid=679298623.
- Interval_scheduling depiction IntervalSelection.svg.
- Interval_scheduling isPrimaryTopicOf Interval_scheduling.