A model for minimizing active processor time

DOI10.1007/s00453-013-9807-yzbMath1314.68085arXiv1208.0312OpenAlexW2013916548MaRDI QIDQ487001

Jessica Chang, Samir Khuller, Harold N. Gabow

Publication date: 19 January 2015

Published in: Algorithmica, Algorithms – ESA 2012 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1208.0312

zbMATH Keywords

schedulingmatchingsactive time

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (10)

Minimum hitting set of interval bundles problem: computational complexity and approximability ⋮ Security-aware database migration planning ⋮ LP rounding and combinatorial algorithms for minimizing active and busy time ⋮ Scheduling Tasks to Minimize Active Time on a Processor with Unlimited Capacity ⋮ Active and Busy Time Scheduling Problem: A Survey ⋮ Complexity and online algorithms for minimum skyline coloring of intervals ⋮ Cost-sharing games in real-time scheduling systems ⋮ Cost-sharing games in real-time scheduling systems ⋮ A new LP rounding algorithm for the active time problem ⋮ On the Price of Anarchy of cost-sharing in real-time scheduling systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel batch scheduling of equal-length jobs with release and due dates
• A linear-time algorithm for a special case of disjoint set union
• Efficient scheduling algorithms for a single batch processing machine
• Matching theory
• A matching problem with side conditions
• Batching identical jobs
• An analysis of the greedy algorithm for the submodular set covering problem
• Scheduling unit-time tasks with integer release times and deadlines
• \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling]
• Scheduling to minimize gaps and power consumption
• An improved approximation algorithm for vertex cover with hard capacities
• Optimal Batch Schedules for Parallel Machines
• Set Cover Revisited: Hypergraph Cover with Hard Capacities
• Minimizing Busy Time in Multiple Machine Real-time Scheduling
• Broadcast scheduling
• Polynomial Time Algorithms for Minimum Energy Scheduling
• Triangle-Free 2-Matchings Revisited
• A robust maximum completion time measure for scheduling
• Scheduling unit tasks to minimize the number of idle periods
• Multiprocessor Scheduling of Unit-Time Jobs with Arbitrary Release Times and Deadlines
• Perfect triangle-free 2-matchings
• An Almost-Linear Algorithm for Two-Processor Scheduling
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Network Flow and Testing Graph Connectivity
• Scheduling Tasks with Nonuniform Deadlines on Two Processors
• Two-Processor Scheduling with Start-Times and Deadlines
• How to Allocate Network Centers
• Proof of the 4/3 conjecture for preemptive vs. nonpreemptive two-processor scheduling
• Faster scaling algorithms for general graph matching problems
• The Capacitated K-Center Problem
• A Fast Algorithm for Multiprocessor Scheduling of Unit-Length Jobs
• Algorithms for power savings
• Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
• An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules
• Optimal Sequencing of Two Equivalent Processors
• Integer Programming and Combinatorial Optimization

This page was built for publication: A model for minimizing active processor time