{"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":"2026-06-02T14:59:26","modified_gmt":"2026-06-02T18:59:26","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":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-100: Sums of Lexicographically Ordered Sets\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n<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\n\n\n<h2 id=\"sums-of-lexicographically-ordered-sets\" class=\"wp-block-heading tr_t1\">Sums of Lexicographically Ordered Sets<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">M.D. Atkinson, A. Negro, N. Santoro<\/div>\n<\/div>\n\n\n\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\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/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":2,"featured_media":0,"parent":11827,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[88],"class_list":["post-12612","page","type-page","status-publish","hentry","cu_page_type-technical-report"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12612","targetHints":{"allow":["GET"]}}],"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\/2"}],"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"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12612"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}