Notice: Function _load_textdomain_just_in_time was called incorrectly. Translation loading for the wp-plugin-hostgator domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114

Notice: Function _load_textdomain_just_in_time was called incorrectly. Translation loading for the ol-scrapes domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893

Warning: Cannot modify header information - headers already sent by (output started at /home4/scienrds/scienceandnerds/wp-includes/functions.php:6114) in /home4/scienrds/scienceandnerds/wp-includes/rest-api/class-wp-rest-server.php on line 1893
{"id":38975,"date":"2024-01-30T21:58:09","date_gmt":"2024-01-30T21:58:09","guid":{"rendered":"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/"},"modified":"2024-01-30T21:58:10","modified_gmt":"2024-01-30T21:58:10","slug":"researchers-approach-new-speed-limit-for-seminal-problem","status":"publish","type":"post","link":"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/","title":{"rendered":"Researchers Approach New Speed Limit for Seminal Problem"},"content":{"rendered":"

Source:https:\/\/www.quantamagazine.org\/researchers-approach-new-speed-limit-for-seminal-problem-20240129\/#comments<\/a><\/br>
\nResearchers Approach New Speed Limit for Seminal Problem<\/br>
\n2024-01-30 21:58:09<\/br><\/p>\n

\n

That\u2019s not to say it\u2019s easy work. It wasn\u2019t until 1983 that the mathematician Hendrik Lenstra<\/a> proved<\/a> that the general problem was even solvable, providing the first algorithm that could do it. Lenstra thought about ILP geometrically. First, he turned the inequalities at the heart of ILP into a convex shape, such as any regular polygon. This shape represents the constraints of the individual problem you\u2019re solving, whether it\u2019s couch production or airline scheduling, so the shape\u2019s interior corresponds to all possible values that could solve the inequalities, and thus the problem. Lenstra called this shape the convex body. The problem\u2019s dimension influences the dimension of this shape: With two variables it takes the form of a flat polygon; in three dimensions it is a Platonic solid<\/a>, and so on.<\/p>\n

Lenstra next imagined all the integers as an infinite set of grid points, known in mathematics as a lattice. A two-dimensional version looks like a sea of dots, and in three dimensions it looks like the points where steel beams in a building connect. The dimension of the lattice also depends on the dimension of a given problem.<\/p>\n

To solve a given ILP problem, Lenstra showed that you just look for where the possible solutions meet the set of integers: at the intersection of the convex body and the lattice. And he came up with an algorithm that could search this space exhaustively \u2014 but to be effective, it sometimes had to break the problem up into pieces of smaller dimensions, adding many steps to the runtime.<\/p>\n

In the following years, several researchers explored how to make this algorithm run faster. In 1988, Ravi Kannan and L\u00e1szl\u00f3 Lov\u00e1sz introduced a concept called the covering radius, borrowed<\/a> from the study of error-correcting codes<\/a>, to help the convex body and lattice intersect more efficiently. Roughly, the covering radius makes sure that the convex body always contains at least one integer point, no matter where you place it on the lattice. As a result, the size of the covering radius also determines how efficiently you can solve the ILP problem.<\/p>\n

So it all came down to determining the size of the ideal covering radius. Unfortunately, this proved to be a hard problem on its own, and the best Kannan and Lov\u00e1sz could do was narrow down a possible value by searching for upper and lower bounds. They showed that the upper bound \u2014 the maximum size of the covering radius \u2014 scaled up linearly with the dimension.<\/em> This was pretty fast, but not enough to significantly speed up the ILP runtime. Over the next 30 years, other researchers could only do slightly better.<\/p>\n

What ultimately helped Reis and Rothvoss break through was an unrelated mathematical result that focused purely on lattices. In 2016, Oded Regev and Stephens-Davidowitz showed<\/a>, in effect, how many lattice points could fit within a specific shape. Reis and Rothvoss applied this to other shapes, which allowed them to better estimate the number of lattice points contained in an ILP covering radius, lowering the upper bound. \u201cThe latest breakthrough came with the realization that you can actually do other kinds of shapes,\u201d Regev said.<\/p>\n

This new tightened upper bound was a vast improvement, allowing Reis and Rothvoss to achieve a dramatic speedup of the overall ILP algorithm. Their work brings the runtime to (log n<\/em>)O<\/sup><\/em>(n<\/em>)<\/sup>, where n<\/em> is the number of variables and O(n)<\/em>means it scales linearly with n<\/em>. (This expression is considered \u201calmost\u201d the same as the run time of the binary problem.)<\/p>\n

\u201cIt\u2019s a triumph at the intersection of math, computer science and geometry,\u201d said Daniel Dadush<\/a> of the national research institute CWI in the Netherlands, who helped pioneer the algorithm Reis and Rothvoss used to measure the ILP runtime.<\/p>\n

For now, the new algorithm hasn\u2019t actually been used to solve any logistical problems, since it would take too much work updating today\u2019s programs to make use of it. But for Rothvoss, that\u2019s beside the point. \u201cIt\u2019s about the theoretical understanding of a problem that has fundamental applications,\u201d he said.<\/p>\n

As to whether the computational efficiency of ILP could be further improved, researchers are still hopeful that they\u2019ll keep approaching the ideal runtime \u2014 but not anytime soon. \u201cThat would require a fundamentally new idea,\u201d Vempala said.<\/span><\/p>\n<\/div>\n

<\/br><\/br><\/br><\/p>\n

Uncategorized<\/br>
\n<\/br>
\nSource:https:\/\/www.quantamagazine.org\/researchers-approach-new-speed-limit-for-seminal-problem-20240129\/#comments<\/a><\/br><\/br><\/p>\n","protected":false},"excerpt":{"rendered":"

Source:https:\/\/www.quantamagazine.org\/researchers-approach-new-speed-limit-for-seminal-problem-20240129\/#comments Researchers Approach New Speed Limit for Seminal Problem 2024-01-30 21:58:09 That\u2019s not to say it\u2019s easy work. It wasn\u2019t until 1983 that the mathematician Hendrik Lenstra proved that the general problem was even solvable, providing the first algorithm that could do it. Lenstra thought about ILP geometrically. First, he turned the inequalities at the […]<\/p>\n","protected":false},"author":1,"featured_media":38976,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","om_disable_all_campaigns":false,"pagelayer_contact_templates":[],"_pagelayer_content":"","_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-38975","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-uncategorized"],"yoast_head":"\nResearchers Approach New Speed Limit for Seminal Problem - Science and Nerds<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Researchers Approach New Speed Limit for Seminal Problem - Science and Nerds\" \/>\n<meta property=\"og:description\" content=\"Source:https:\/\/www.quantamagazine.org\/researchers-approach-new-speed-limit-for-seminal-problem-20240129\/#comments Researchers Approach New Speed Limit for Seminal Problem 2024-01-30 21:58:09 That\u2019s not to say it\u2019s easy work. It wasn\u2019t until 1983 that the mathematician Hendrik Lenstra proved that the general problem was even solvable, providing the first algorithm that could do it. Lenstra thought about ILP geometrically. First, he turned the inequalities at the […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/\" \/>\n<meta property=\"og:site_name\" content=\"Science and Nerds\" \/>\n<meta property=\"article:published_time\" content=\"2024-01-30T21:58:09+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-01-30T21:58:10+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/scienceandnerds.com\/wp-content\/uploads\/2024\/01\/researchers-approach-new-speed-limit-for-seminal-problem_65b970f1f242a.webp\" \/>\n\t<meta property=\"og:image:width\" content=\"2560\" \/>\n\t<meta property=\"og:image:height\" content=\"1440\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/webp\" \/>\n<meta name=\"author\" content=\"admin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/\",\"url\":\"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/\",\"name\":\"Researchers Approach New Speed Limit for Seminal Problem - Science and Nerds\",\"isPartOf\":{\"@id\":\"https:\/\/scienceandnerds.com\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2024\/01\/researchers-approach-new-speed-limit-for-seminal-problem_65b970f1f242a.webp?fit=2560%2C1440&ssl=1\",\"datePublished\":\"2024-01-30T21:58:09+00:00\",\"dateModified\":\"2024-01-30T21:58:10+00:00\",\"author\":{\"@id\":\"https:\/\/scienceandnerds.com\/#\/schema\/person\/ea2991abeb2b9ab04b32790dff28360e\"},\"breadcrumb\":{\"@id\":\"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/#primaryimage\",\"url\":\"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2024\/01\/researchers-approach-new-speed-limit-for-seminal-problem_65b970f1f242a.webp?fit=2560%2C1440&ssl=1\",\"contentUrl\":\"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2024\/01\/researchers-approach-new-speed-limit-for-seminal-problem_65b970f1f242a.webp?fit=2560%2C1440&ssl=1\",\"width\":2560,\"height\":1440},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/scienceandnerds.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Researchers Approach New Speed Limit for Seminal Problem\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/scienceandnerds.com\/#website\",\"url\":\"https:\/\/scienceandnerds.com\/\",\"name\":\"Science and Nerds\",\"description\":\"My WordPress Blog\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/scienceandnerds.com\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/scienceandnerds.com\/#\/schema\/person\/ea2991abeb2b9ab04b32790dff28360e\",\"name\":\"admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/scienceandnerds.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/7e6e14fc6691445ef2b2c0a3a6c43882?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/7e6e14fc6691445ef2b2c0a3a6c43882?s=96&d=mm&r=g\",\"caption\":\"admin\"},\"sameAs\":[\"https:\/\/scienceandnerds.com\"],\"url\":\"https:\/\/scienceandnerds.com\/author\/admin\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Researchers Approach New Speed Limit for Seminal Problem - Science and Nerds","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:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/","og_locale":"en_US","og_type":"article","og_title":"Researchers Approach New Speed Limit for Seminal Problem - Science and Nerds","og_description":"Source:https:\/\/www.quantamagazine.org\/researchers-approach-new-speed-limit-for-seminal-problem-20240129\/#comments Researchers Approach New Speed Limit for Seminal Problem 2024-01-30 21:58:09 That\u2019s not to say it\u2019s easy work. It wasn\u2019t until 1983 that the mathematician Hendrik Lenstra proved that the general problem was even solvable, providing the first algorithm that could do it. Lenstra thought about ILP geometrically. First, he turned the inequalities at the […]","og_url":"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/","og_site_name":"Science and Nerds","article_published_time":"2024-01-30T21:58:09+00:00","article_modified_time":"2024-01-30T21:58:10+00:00","og_image":[{"width":2560,"height":1440,"url":"https:\/\/scienceandnerds.com\/wp-content\/uploads\/2024\/01\/researchers-approach-new-speed-limit-for-seminal-problem_65b970f1f242a.webp","type":"image\/webp"}],"author":"admin","twitter_card":"summary_large_image","twitter_misc":{"Written by":"admin","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/","url":"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/","name":"Researchers Approach New Speed Limit for Seminal Problem - Science and Nerds","isPartOf":{"@id":"https:\/\/scienceandnerds.com\/#website"},"primaryImageOfPage":{"@id":"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/#primaryimage"},"image":{"@id":"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/#primaryimage"},"thumbnailUrl":"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2024\/01\/researchers-approach-new-speed-limit-for-seminal-problem_65b970f1f242a.webp?fit=2560%2C1440&ssl=1","datePublished":"2024-01-30T21:58:09+00:00","dateModified":"2024-01-30T21:58:10+00:00","author":{"@id":"https:\/\/scienceandnerds.com\/#\/schema\/person\/ea2991abeb2b9ab04b32790dff28360e"},"breadcrumb":{"@id":"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/#primaryimage","url":"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2024\/01\/researchers-approach-new-speed-limit-for-seminal-problem_65b970f1f242a.webp?fit=2560%2C1440&ssl=1","contentUrl":"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2024\/01\/researchers-approach-new-speed-limit-for-seminal-problem_65b970f1f242a.webp?fit=2560%2C1440&ssl=1","width":2560,"height":1440},{"@type":"BreadcrumbList","@id":"https:\/\/scienceandnerds.com\/2024\/01\/30\/researchers-approach-new-speed-limit-for-seminal-problem\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/scienceandnerds.com\/"},{"@type":"ListItem","position":2,"name":"Researchers Approach New Speed Limit for Seminal Problem"}]},{"@type":"WebSite","@id":"https:\/\/scienceandnerds.com\/#website","url":"https:\/\/scienceandnerds.com\/","name":"Science and Nerds","description":"My WordPress Blog","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/scienceandnerds.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/scienceandnerds.com\/#\/schema\/person\/ea2991abeb2b9ab04b32790dff28360e","name":"admin","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/scienceandnerds.com\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/7e6e14fc6691445ef2b2c0a3a6c43882?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/7e6e14fc6691445ef2b2c0a3a6c43882?s=96&d=mm&r=g","caption":"admin"},"sameAs":["https:\/\/scienceandnerds.com"],"url":"https:\/\/scienceandnerds.com\/author\/admin\/"}]}},"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/i0.wp.com\/scienceandnerds.com\/wp-content\/uploads\/2024\/01\/researchers-approach-new-speed-limit-for-seminal-problem_65b970f1f242a.webp?fit=2560%2C1440&ssl=1","_links":{"self":[{"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/posts\/38975","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/comments?post=38975"}],"version-history":[{"count":1,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/posts\/38975\/revisions"}],"predecessor-version":[{"id":38977,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/posts\/38975\/revisions\/38977"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/media\/38976"}],"wp:attachment":[{"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/media?parent=38975"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/categories?post=38975"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scienceandnerds.com\/wp-json\/wp\/v2\/tags?post=38975"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}