Abstract
A linear extension of a poset P=(X,≺) is a permutation x 1,x 2,…,x |X| of X such that i<j whenever x i ≺x j . For a given poset P=(X,≺) and a cost function c(x,y) defined on X×X, we want to find a linear extension of P such that maximum cost is as small as possible. For the general case, it is NP-complete. In this paper we consider the linear extension problem with the assumption that c(x,y)=0 whenever x and y are incomparable. First, we prove the discussed problem is polynomially solvable for a special poset. And then, we present a polynomial algorithm to obtain an approximate solution.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Duffus D, Rival I, Winkler P (1982) Minimizing setups for cycle-free ordered sets. Proc Am Math Soc 85:509–513
Fishburn PC, Gehrlein WV (1986) Minimizing bumps in linear extensions of ordered sets. Order 3:3–14
Ghazal H, Sharary A, Zaguia N (1988) On minimizing jump number for interval orders. Order 4:341–350
Habib M, Mohring RH, Steiner G (1988) Computing the Bump number is easy. Order 5:107–109
Liu L, Wu B, Yao E (2011) Minimizing the sum cost in linear extensions of a poset. J Comb Optim 21:247–253
Schaffer AA, Simons BB (1988) Computing the Bump number with techniques form two-processor scheduling. Order 5:131–141
Syslo MM (1984) Minimizing the jump number for partially-ordered sets: a graph-theoretic approach. Order 1:7–20
Wu B, Yao E, Liu L (2011) A polynomially solvable case of optimal linear extension problem of a poset. J Comb Optim 20:422–428
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is supported by National Nature Science Foundation of China (Grant No. 10971191, 11001232), Fundamental Research Funds for the Central Universities (Grant No. 2010121004) and Department of Education of Zhejiang Province of China (Y200909535).
Rights and permissions
About this article
Cite this article
Wu, B., Liu, L. & Yao, E. Minimizing the maximum bump cost in linear extensions of a poset. J Comb Optim 26, 509–519 (2013). https://doi.org/10.1007/s10878-012-9456-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-012-9456-0