Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine
From MaRDI portal
Publication:4268700
DOI10.1137/S0097539796305778zbMath0926.68014OpenAlexW2069466073MaRDI QIDQ4268700
Publication date: 28 October 1999
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539796305778
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Parallel algorithms in computer science (68W10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items
Managing the ship movements in the Port of Venice, SPT is optimally competitive for uniprocessor flow, Single machine batch scheduling with release times and delivery costs, Joint replenishment meets scheduling, A best possible online algorithm for minimizing the total completion time and the total soft penalty cost, Improving the preemptive bound for the one-machine dynamic total completion time scheduling problem., Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time, Non-Preemptive Flow-Time Minimization via Rejections, Fixed-Parameter Approximation Schemes for Weighted Flowtime., Temperature aware online algorithms for minimizing flow time, Temperature Aware Online Algorithms for Minimizing Flow Time, Coupling genetic local search and recovering beam search algorithms for minimizing the total completion time in the single machine scheduling problem subject to release dates, From Preemptive to Non-preemptive Scheduling Using Rejections, Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time, Randomized algorithms for on-line scheduling problems: How low can't you go?
