On-line scheduling with monotone subsequence constraints

DOI10.1016/j.tcs.2018.09.004zbMath1429.90026OpenAlexW2889758147MaRDI QIDQ2319898

Kelin Luo, Hui-Li Zhang, Yin-Feng Xu

Publication date: 20 August 2019

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

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

zbMATH Keywords

competitive analysisonline schedulingmonotone subsequence

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Online algorithms; streaming algorithms (68W27)

Cites Work

• Enumerating longest increasing subsequences and patience sorting
• Optimal online selection of a monotone subsequence: a central limit theorem
• Competitive analysis of preemptive single-machine scheduling
• An algorithm for solving the longest increasing circular subsequence problem
• On computing the length of longest increasing subsequences
• Longest increasing subsequences in sliding windows
• Fast computation of a longest increasing subsequence and application
• Permutations, matrices, and generalized Young tableaux
• The Surprising Mathematics of Longest Increasing Subsequences
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• Beyond Competitive Analysis
• A New Approach to Online Scheduling
• Tight Bounds for Permutation Flow Shop Scheduling