{"id":12612,"date":"2021-11-14T20:01:22","date_gmt":"2021-11-15T01:01:22","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12612"},"modified":"2021-11-14T20:01:22","modified_gmt":"2021-11-15T01:01:22","slug":"tr-100-sums-of-lexicographically-ordered-sets","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-100-sums-of-lexicographically-ordered-sets\/","title":{"rendered":"TR-100: Sums of Lexicographically Ordered Sets"},"content":{"rendered":"<p>Carleton University<br \/>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/\">Technical Report<\/a> <strong>TR-100<\/strong><br \/>\nMay 1987<\/p>\n<h2 class=\"tr_t1\">Sums of Lexicographically Ordered Sets<\/h2>\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">M.D. Atkinson, A. Negro, N. Santoro<\/div>\n<\/div>\n<div>\n<h3>Abstract<\/h3>\n<p>We consider the problem of determining finite integer sets which are knapsack-solvable in linear time (i.e., it is possible to determine in linear time, for any integer b, whether b can be expressed as a sum of distinct elements of that set) and where the largest element is as small as possible. We study the condition that the k-subsets (for fixed k) when lexicographically ordered have increasing sums. We give an optimal construction of sets with this property, prove that it is unique, and give the asymptotic behaviour of the largest member. Using these results, we construct sequences of positive integers where the largest element is minimal, the subset sums are distinct and lexicographically ordered, and are knapsack-solvable in linear time.<\/p>\n<\/div>\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/TR-100.pdf\">TR-100<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-100 May 1987 Sums of Lexicographically Ordered Sets M.D. Atkinson, A. Negro, N. Santoro Abstract We consider the problem of determining finite integer sets which are knapsack-solvable in linear time (i.e., it is possible to determine in linear time, for any integer b, whether b can be expressed as a sum [&hellip;]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":11827,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v21.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>TR-100: Sums of Lexicographically Ordered Sets - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-100 May 1987 Sums of Lexicographically Ordered Sets M.D. Atkinson, A. Negro, N. Santoro Abstract We consider the\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-100-sums-of-lexicographically-ordered-sets\/\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-100-sums-of-lexicographically-ordered-sets\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-100-sums-of-lexicographically-ordered-sets\/\",\"name\":\"TR-100: Sums of Lexicographically Ordered Sets - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-11-15T01:01:22+00:00\",\"dateModified\":\"2021-11-15T01:01:22+00:00\",\"description\":\"Carleton University Technical Report TR-100 May 1987 Sums of Lexicographically Ordered Sets M.D. Atkinson, A. Negro, N. Santoro Abstract We consider the\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-100-sums-of-lexicographically-ordered-sets\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-100-sums-of-lexicographically-ordered-sets\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-100-sums-of-lexicographically-ordered-sets\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/carleton.ca\/scs\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Research\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"SCS Technical Reports\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Technical Reports 1987\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-100: Sums of Lexicographically Ordered Sets\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/carleton.ca\/scs\/#website\",\"url\":\"https:\/\/carleton.ca\/scs\/\",\"name\":\"School of Computer Science\",\"description\":\"Carleton University\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/carleton.ca\/scs\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"TR-100: Sums of Lexicographically Ordered Sets - School of Computer Science","description":"Carleton University Technical Report TR-100 May 1987 Sums of Lexicographically Ordered Sets M.D. Atkinson, A. Negro, N. Santoro Abstract We consider the","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-100-sums-of-lexicographically-ordered-sets\/","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-100-sums-of-lexicographically-ordered-sets\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-100-sums-of-lexicographically-ordered-sets\/","name":"TR-100: Sums of Lexicographically Ordered Sets - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-11-15T01:01:22+00:00","dateModified":"2021-11-15T01:01:22+00:00","description":"Carleton University Technical Report TR-100 May 1987 Sums of Lexicographically Ordered Sets M.D. Atkinson, A. Negro, N. Santoro Abstract We consider the","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-100-sums-of-lexicographically-ordered-sets\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-100-sums-of-lexicographically-ordered-sets\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/tr-100-sums-of-lexicographically-ordered-sets\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/carleton.ca\/scs\/"},{"@type":"ListItem","position":2,"name":"Research","item":"https:\/\/carleton.ca\/scs\/research\/"},{"@type":"ListItem","position":3,"name":"SCS Technical Reports","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/"},{"@type":"ListItem","position":4,"name":"Technical Reports 1987","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1987\/"},{"@type":"ListItem","position":5,"name":"TR-100: Sums of Lexicographically Ordered Sets"}]},{"@type":"WebSite","@id":"https:\/\/carleton.ca\/scs\/#website","url":"https:\/\/carleton.ca\/scs\/","name":"School of Computer Science","description":"Carleton University","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/carleton.ca\/scs\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"}]}},"acf":{"banner_image_type":"none","banner_button":"no"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12612"}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/49"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12612"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12612\/revisions"}],"predecessor-version":[{"id":12613,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12612\/revisions\/12613"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11827"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12612"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}