Abstract
Let (X, <) be a partially ordered set. A linear extension x 1, x 2, ... has a bump whenever x i<x i+1, and it has a jump whenever x iand x i+1are incomparable. The problem of finding a linear erxtension that minimizes the number of jumps has been studied extensively; Pulleyblank shows that it is NP-complete in the general case. Fishburn and Gehrlein raise the question of finding a linear extension that minimizes the number of bumps. We show that the bump number problem is closely related to the well-studied problem of scheduling unit-time tasks with a precedence partial order on two identical processors. We point out that a variant of Gabow's linear-time algorithm for the two-processor scheduling problem solves the bump number problem. Habib, Möhring, and Steiner have independently discovered a different polynomial-time algorithm to solve the bump number problem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
John Bruno, John W. JonesIII, and Kimming So (1980) Deterministic scheduling with pipe-lined processors, IEEE Transactions on Computers C-29, 308–316.
E.G. CoffmanJr. and R.L. Graham (1972) Optimal scheduling for two-processor systems, Acta Informatica 1, 200–213.
Peter C. Fishburn and William V. Gehrlein (1986) Minimizing bumps in linear extensions of ordered sets, Order 3, 3–14.
M. Fuji, T. Kasami, and K. Ninomiya (1969, 1971) Optimal sequencing of two equivalent processors, SIAM J. Appl. Math. 17, 784–789; Erratum SIAM J. Appl. Math. 20, 141.
Harold N. Gabow (1982) An almost-linear algorithm for two-processor scheduling, J. ACM 29, 766–780.
Harold N. Gabow (to appear) Scheduling UET systems on two uniform processors and length two pipelines, SIAM J. Comp.
Harold N. Gabow and Robert E. Tarjan (1983, 1985) A linear- time algorithm for a special case of disjoint set union, 15th Annual ACM Symposium on Theory of Computing, pp. 246–251 and J. Comp. and Syst. Sci. 30, 209–221.
Michel Habib, Rolf H. Möhring, and George Steiner (1988) Computing the bump number is easy, Order 5, 107–129.
David Helmbold and Ernst Mayr (1986, 1987) Two processor scheduling is in NC, VLSI Algorithms and Architectures: Aegean Workshop on Computing, 1986, Lecture Notes in Computer Science, Vol. 227, Springer-Verlag, pp. 12–25 and SIAM J. Comp. 17, 747–759.
Eugene Lawler, Jan Karel Lenstra, Charles Martel, Barbara Simons, and Larry Stockmeyer (1987) Pipeline scheduling: a survey, IBM Research Report RJ5738, submitted for publication.
Joseph Y-T. Leung, Oliver Vornberger, and James D. Witthoff (1984), On some variants of the bandwith minimization problem, SIAM J. Comp. 13, 650–667.
W. R. Pulleyblank (to appear) On minimizing setups in precedence constrained scheduling, Discr. Appl. Math. (cited in [3]).
Author information
Authors and Affiliations
Additional information
Part of this work was done while the first author was a Research Student Associate at IBM Almaden Research Center. During the academic year his work is primarily supported by a Fannie and John Hertz Foundation Fellowship and is supported in part by ONR contract N00014-85-C-0731.
Rights and permissions
About this article
Cite this article
Schäffer, A.A., Simons, B.B. Computing the bump number with techniques from two-processor scheduling. Order 5, 131–141 (1988). https://doi.org/10.1007/BF00337618
Issue Date:
DOI: https://doi.org/10.1007/BF00337618