10 citations · 31 across the 24 of their papers we have counts for
Showing 2012Show all
2 papers · 1 filter
cs.DS2012
Dual techniques for scheduling on a machine with varying speed
Nicole Megow, José Verschae
We study scheduling problems on a machine with varying speed. Assuming a known speed function we ask for a cost-efficient scheduling solution. Our main result is a PTAS for minimiz…
cs.DS2012
A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio
Elisabeth Günther, Olaf Maurer, Nicole Megow +1
We propose a new approach to competitive analysis in online scheduling by introducing the novel concept of competitive-ratio approximation schemes. Such a scheme algorithmically co…