加权拟阵贪心算法的正确性 A task-scheduling problem ·定理: The greedy algorithm on matroid is Unit-time task: a task need unit time to correct 证明: is just the combination of the last chedule of task set S: is a permutation of lemmas and corollaries S specifying the order in which these tasks to be perfo Scheduling unit-time task with deadlines and penalties for a single processor 清华大学們学院宋恒 清华大学软件学院宋 Input of the problem Convert the problem to a matroid A set of task S=(a, a2,..., an] Independent tasks: if there exists a A set of integer deadlines d, d2,..., d schedule for these tasks such that no A set of nonnegative weights of penalties tasks are late such that if task a is I =all subsets of independent tasks finished before its deadlines there will · S is the set of all tasks incur a penalty wi. ·M={S,l} is a matroid 清华大学学院未恒 清华大学软件学院宋 拟阵小结 拟阵定义 拟阵实例 拟阵的简单性质 加权拟阵 加权拟阵的优化问题及其变种 ·上述问题的最优子结构 ·上述问题的贪婪选择律 贪婪算法,及其在最小支撑树的应用 清华大学轼字院宋恒9 清华大学软件学院宋斌恒 49 加权拟阵贪心算法的正确性 •定理：The greedy algorithm on matroid is correct •证明: is just the combination of the last lemmas and corollaries. 清华大学软件学院宋斌恒 50 A task-scheduling problem •Unit-time task: A task need unit time to complete •Schedule of task set S: is a permutation of S specifying the order in which these tasks are to be performed •Scheduling unit-time task with deadlines and penalties for a single processor: 清华大学软件学院宋斌恒 51 Input of the problem •A set of task S={a1 ,a2 ,… ,an } •A set of integer deadlines d1 ,d2 ,… ,dn . •A set of nonnegative weights of penalties: w1 ,w2 ,… ,wn , such that if task ai is not finished before its deadlines there will incur a penalty wi . 清华大学软件学院宋斌恒 52 Convert the problem to a matroid •Independent tasks:if there exists a schedule for these tasks such that no tasks are late. • l ={all subsets of independent tasks} • S is the set of all tasks • M={S, l } is a matroid 清华大学软件学院宋斌恒 53 拟阵小结 •拟阵定义 •拟阵实例 •拟阵的简单性质 •加权拟阵 •加权拟阵的优化问题及其变种 •上述问题的最优子结构 •上述问题的贪婪选择律 •贪婪算法，及其在最小支撑树的应用