{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T04:30:59Z","timestamp":1742963459245,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319411132"},{"type":"electronic","value":"9783319411149"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-41114-9_2","type":"book-chapter","created":{"date-parts":[[2016,6,27]],"date-time":"2016-06-27T10:05:14Z","timestamp":1467021914000},"page":"18-28","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems"],"prefix":"10.1007","author":[{"given":"Gabriel","family":"Istrate","sequence":"first","affiliation":[]},{"given":"Cosmin","family":"Bonchi\u015f","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,6,28]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"Byers, J., Heeringa, B., Mitzenmacher, M., Zervas, G.: Heapable sequences and subseqeuences. In: Proceedings of ANALCO, pp. 33\u201344 (2011)","DOI":"10.1137\/1.9781611973013.4"},{"key":"2_CR2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139872003","volume-title":"The Surprising Mathematics of Longest Increasing Subsequences","author":"D Romik","year":"2015","unstructured":"Romik, D.: The Surprising Mathematics of Longest Increasing Subsequences, vol. 4. Cambridge University Press, New York (2015)"},{"key":"2_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/978-3-319-19929-0_22","volume-title":"Combinatorial Pattern Matching","author":"G Istrate","year":"2015","unstructured":"Istrate, G., Bonchi\u015f, C.: Partition into heapable sequences, heap tableaux and a multiset extension of hammersley\u2019s process. In: Cicalese, F., Porat, E., Vaccaro, U. (eds.) CPM 2015. LNCS, vol. 9133, pp. 261\u2013271. Springer, Heidelberg (2015)"},{"key":"2_CR4","unstructured":"Porfilio, J.: A combinatorial characterization of heapability. Master\u2019s thesis. Williams College, May 2015. http:\/\/library.williams.edu\/theses\/pdf.php?id=790"},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"161","DOI":"10.2307\/1969503","volume":"51","author":"RP Dilworth","year":"1950","unstructured":"Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. Math. 51, 161\u2013166 (1950)","journal-title":"Ann. Math."},{"issue":"2","key":"2_CR6","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0012-365X(85)90045-7","volume":"55","author":"A Gy\u00e1rf\u00e1s","year":"1985","unstructured":"Gy\u00e1rf\u00e1s, A., Lehel, J.: Covering and coloring problems for relatives of intervals. Discrete Math. 55(2), 167\u2013180 (1985)","journal-title":"Discrete Math."},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Brightwell, G.: Models of random partial orders. In: Surveys in Combinatorics, pp. 53\u201383 (1993)","DOI":"10.1017\/CBO9780511662089.004"},{"issue":"4","key":"2_CR8","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/BF00582738","volume":"1","author":"P Winkler","year":"1985","unstructured":"Winkler, P.: Random orders. Order 1(4), 317\u2013331 (1985)","journal-title":"Order"},{"key":"2_CR9","volume-title":"Theory of linear and integer programming","author":"A Schrijver","year":"1998","unstructured":"Schrijver, A.: Theory of linear and integer programming. Wiley, New York (1998)"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Hammersley, J.M., et al.: A few seedlings of research. In: Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Theory of Statistics (1972)","DOI":"10.1525\/9780520325883-020"},{"issue":"2","key":"2_CR11","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/0001-8708(77)90030-5","volume":"26","author":"BF Logan","year":"1977","unstructured":"Logan, B.F., Shepp, L.A.: A variational problem for random Young tableaux. Adv. Math. 26(2), 206\u2013222 (1977)","journal-title":"Adv. Math."},{"issue":"6","key":"2_CR12","first-page":"1024","volume":"233","author":"A Vershik","year":"1977","unstructured":"Vershik, A., Kerov, S.V.: Asymptotics of plancherel measure of symmetrical group and limit form of Young tables. Doklady Akademii Nauk SSSR 233(6), 1024\u20131027 (1977)","journal-title":"Doklady Akademii Nauk SSSR"},{"issue":"2","key":"2_CR13","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/BF01204214","volume":"103","author":"D Aldous","year":"1995","unstructured":"Aldous, D., Diaconis, P.: Hammersley\u2019s interacting particle process and longest increasing subsequences. Probab. Theory Relat. Fields 103(2), 199\u2013213 (1995)","journal-title":"Probab. Theory Relat. Fields"},{"issue":"4","key":"2_CR14","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF00420352","volume":"9","author":"G Brightwell","year":"1992","unstructured":"Brightwell, G.: Random k-dimensional orders: Width and number of linear extensions. Order 9(4), 333\u2013342 (1992)","journal-title":"Order"},{"issue":"2","key":"2_CR15","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1090\/S0002-9939-1988-0943043-6","volume":"103","author":"B Bollob\u00e1s","year":"1988","unstructured":"Bollob\u00e1s, B., Winkler, P.: The longest chain among random points in euclidean space. Proc. Am. Math. Soc. 103(2), 347\u2013353 (1988)","journal-title":"Proc. Am. Math. Soc."},{"issue":"4","key":"2_CR16","doi-asserted-by":"publisher","first-page":"1009","DOI":"10.1214\/aoap\/1177005586","volume":"2","author":"B Bollob\u00e1s","year":"1992","unstructured":"Bollob\u00e1s, B., Brightwell, G.: The height of a random partial order: Concentration of measure. Ann. Appl. Probab. 2(4), 1009\u20131018 (1992)","journal-title":"Ann. Appl. Probab."},{"issue":"1","key":"2_CR17","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0377-0427(01)00461-7","volume":"142","author":"P Groeneboom","year":"2002","unstructured":"Groeneboom, P.: Hydrodynamical methods for analyzing longest increasing subsequences. J. Comput. Appl. Math. 142(1), 83\u2013105 (2002)","journal-title":"J. Comput. Appl. Math."},{"issue":"4","key":"2_CR18","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s00493-011-2842-8","volume":"34","author":"N Linial","year":"2014","unstructured":"Linial, N., Luria, Z.: An upper bound on the number of high-dimensional permutations. Combinatorica 34(4), 471\u2013486 (2014)","journal-title":"Combinatorica"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Linial, N., Simkin, M.: Monotone subsequences in high-dimensional permutations. arXiv preprint arXiv:1602.02719 (2016)","DOI":"10.1017\/S0963548317000517"},{"key":"2_CR20","unstructured":"Cardinal, J., Fiorini, S., van Assche, G.: On minimum entropy graph colorings. In: Proceedings of ISIT 2004, The International Symposium on Information Theory, p. 43 (2004)"},{"issue":"2\u20133","key":"2_CR21","first-page":"340","volume":"348","author":"E Halperin","year":"2005","unstructured":"Halperin, E., Karp, R.: The minimum entropy set cover problem. Theor. Comput. Sci. 348(2\u20133), 340\u2013350 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"2_CR22","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s00453-007-9076-8","volume":"51","author":"J Cardinal","year":"2008","unstructured":"Cardinal, J., Fiorini, S., Joraet, G.: Tight results on minimum entropy set cover. Algorithmica 51(1), 49\u201360 (2008)","journal-title":"Algorithmica"},{"issue":"6","key":"2_CR23","doi-asserted-by":"publisher","first-page":"680","DOI":"10.1016\/j.orl.2008.06.010","volume":"36","author":"J Cardinal","year":"2008","unstructured":"Cardinal, J., Fiorini, S., Joret, G.: Minimum entropy orientations. Oper. Res. Lett. 36(6), 680\u2013683 (2008)","journal-title":"Oper. Res. Lett."},{"key":"2_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/978-3-642-03073-4_9","volume-title":"Mathematical Theory and Computational Practice","author":"J Cardinal","year":"2009","unstructured":"Cardinal, J., Fiorini, S., Joret, G.: Minimum entropy combinatorial optimization problems. In: Ambos-Spies, K., L\u00f6we, B., Merkle, W. (eds.) CiE 2009. LNCS, vol. 5635, pp. 79\u201388. Springer, Heidelberg (2009)"},{"key":"2_CR25","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1016\/j.ic.2015.04.003","volume":"242","author":"M Kova\u010devi\u0107","year":"2015","unstructured":"Kova\u010devi\u0107, M., Stanojevi\u0107, I., \u0160enk, V.: On the entropy of couplings. Inf. Comput. 242, 369\u2013382 (2015)","journal-title":"Inf. Comput."},{"key":"2_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-319-30000-9_23","volume-title":"Language and Automata Theory and Applications","author":"G Istrate","year":"2016","unstructured":"Istrate, G., Bonchi\u015f, C., Dinu, L.P.: The minimum entropy submodular set cover problem. In: Dediu, A.-H., Janou\u0161ek, J., Mart\u00edn-Vide, C., Truthe, B. (eds.) LATA 2016. LNCS, vol. 9618, pp. 295\u2013306. Springer, Heidelberg (2016)"},{"key":"2_CR27","doi-asserted-by":"publisher","first-page":"1329","DOI":"10.1109\/18.532875","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Orlitsky, A.: Source coding and graph entropies. IEEE Trans. Inform. Theory 42, 1329\u20131339 (1995). Citeseer","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"8","key":"2_CR28","doi-asserted-by":"publisher","first-page":"3901","DOI":"10.1109\/TIT.2010.2050835","volume":"56","author":"V Doshi","year":"2010","unstructured":"Doshi, V., Shah, D., M\u00e9dard, M., Effros, M.: Functional compression through graph coloring. IEEE Trans. Inf. Theory 56(8), 3901\u20133917 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2_CR29","doi-asserted-by":"crossref","unstructured":"Barbay, J., Munro, J.I.: Succinct encoding of permutations : Applications to text indexing. In: Encyclopedia of Algorithms, pp. 915\u2013919. Springer (2008)","DOI":"10.1007\/978-0-387-30162-4_411"},{"key":"2_CR30","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.tcs.2013.10.019","volume":"513","author":"J Barbay","year":"2013","unstructured":"Barbay, J., Navarro, G.: On compressing permutations and adaptive sorting. Theoret. Comput. Sci. 513, 109\u2013123 (2013)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-41114-9_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,2]],"date-time":"2022-07-02T06:48:56Z","timestamp":1656744536000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-41114-9_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319411132","9783319411149"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-41114-9_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"28 June 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}