Optimal semi-online algorithms for machine covering

DOI10.1016/J.TCS.2006.11.015zbMATH Open1108.68023OpenAlexW1987709673MaRDI QIDQ870840FDOQ870840

Authors: Zhiyi Tan, Yong Wu 

Publication date: 15 March 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.11.015

Recommendations

• SEMI-ONLINE MACHINE COVERING
• Approximation and Online Algorithms
• Optimal semi-online algorithm for machine covering with nonsimultaneous machine available times
• Optimal algorithms for semi-online machine covering on two hierarchical machines
• Online, semi-online algorithms for machine covering with non-simultaneous machine available time

zbMATH Keywords

schedulingcompetitive ratiosemi-onlinedesign and analysis of algorithms

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites Work

• Semi-on-line multiprocessor scheduling with given total processing time
• The exact LPT-bound for maximizing the minimum completion time
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• On-line machine covering
• Semi on-line scheduling on two identical machines
• Bin stretching revisited
• The optimal on-line parallel machine scheduling
• Semi on-line algorithms for the partition problem
• Semi-on-line problems on two identical machines with combined partial information
• Semi-online algorithms for parallel machine scheduling problems
• Semi-online scheduling with decreasing job sizes
• On-line bin-stretching
• Randomized on-line and semi-on-line scheduling on identical machines
• Semi-on-line scheduling problems for maximizing the minimum machine completion time

Cited In (13)

• Machine covering with combined partial information
• Online maximum \(k\)-coverage
• Improved approaches to the exact solution of the machine covering problem
• SEMI-ONLINE MACHINE COVERING
• Approximation and Online Algorithms
• Semi-online machine covering for two uniform machines
• Optimal Semi-online Scheduling Algorithms on a Small Number of Machines
• Semi-online scheduling: a survey
• Online, semi-online algorithms for machine covering with non-simultaneous machine available time
• Optimal semi-online algorithm for machine covering with nonsimultaneous machine available times
• Fair division of indivisible goods: recent progress and open questions
• A better semi-online algorithm for \(\mathrm Q3/s_{1} = s_{2}\leq s_{3}/C_{\mathrm{min}}\) with the known largest size
• Optimal algorithms for semi-online machine covering on two hierarchical machines

This page was built for publication: Optimal semi-online algorithms for machine covering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870840)