{"id":12801,"date":"2021-11-21T17:05:30","date_gmt":"2021-11-21T22:05:30","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12801"},"modified":"2021-11-21T17:05:30","modified_gmt":"2021-11-21T22:05:30","slug":"tr-95-22-approximate-maxima-finding-of-continuous-functions-under-restricted-budget","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-22-approximate-maxima-finding-of-continuous-functions-under-restricted-budget\/","title":{"rendered":"TR-95-22: Approximate Maxima Finding of Continuous Functions under Restricted Budget"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-95-22
\nNovember 1995<\/p>\n

Approximate Maxima Finding of Continuous Functions under Restricted Budget<\/h2>\n
\n
\n
\n
\n
\n
Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, David Peleg<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n
\n

A function is distributed among nodes of a graph in a continuous way, i.e., such that the di\u000berence between values stored at adjacent nodes is small. The goal is to \fnd a node of maximum value by probing some nodes under a restricted budget. Every node has an associated cost which has to be paid for probing it and a probe reveals the value of the node. If the total budget is too small to allow probing every node, it is impossible to \fnd the maximum value in the worst case. Hence we seek an Approximate Maxima Finding (AMF) algorithm that o\u000bers the best worst-case guarantee g, i.e., for any continuous distribution of values it \fnds a node whose value di\u000bers from the maximum value by at most g.Approximate Maxima Finding in graphs is related to a generalization of the multi-center problem and we get new results for this problem as well. For example, we givea polynomial algorithm to \fnd a minimum cost solution for the multicenter problem on a tree, with arbitrary node costs.<\/p>\n<\/div>\n

TR-95-22.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-95-22 November 1995 Approximate Maxima Finding of Continuous Functions under Restricted Budget Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, David Peleg Abstract A function is distributed among nodes of a graph in a continuous way, i.e., such that the di\u000berence between values stored at adjacent nodes is small. The goal is to […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":11736,"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":"\nTR-95-22: Approximate Maxima Finding of Continuous Functions under Restricted Budget - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-95-22 November 1995 Approximate Maxima Finding of Continuous Functions under Restricted Budget Evangelos Kranakis,\" \/>\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-1995\/tr-95-22-approximate-maxima-finding-of-continuous-functions-under-restricted-budget\/\" \/>\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-1995\/tr-95-22-approximate-maxima-finding-of-continuous-functions-under-restricted-budget\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-22-approximate-maxima-finding-of-continuous-functions-under-restricted-budget\/\",\"name\":\"TR-95-22: Approximate Maxima Finding of Continuous Functions under Restricted Budget - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-11-21T22:05:30+00:00\",\"dateModified\":\"2021-11-21T22:05:30+00:00\",\"description\":\"Carleton University Technical Report TR-95-22 November 1995 Approximate Maxima Finding of Continuous Functions under Restricted Budget Evangelos Kranakis,\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-22-approximate-maxima-finding-of-continuous-functions-under-restricted-budget\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-22-approximate-maxima-finding-of-continuous-functions-under-restricted-budget\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-22-approximate-maxima-finding-of-continuous-functions-under-restricted-budget\/#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 1995\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-95-22: Approximate Maxima Finding of Continuous Functions under Restricted Budget\"}]},{\"@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-95-22: Approximate Maxima Finding of Continuous Functions under Restricted Budget - School of Computer Science","description":"Carleton University Technical Report TR-95-22 November 1995 Approximate Maxima Finding of Continuous Functions under Restricted Budget Evangelos Kranakis,","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-1995\/tr-95-22-approximate-maxima-finding-of-continuous-functions-under-restricted-budget\/","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-1995\/tr-95-22-approximate-maxima-finding-of-continuous-functions-under-restricted-budget\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-22-approximate-maxima-finding-of-continuous-functions-under-restricted-budget\/","name":"TR-95-22: Approximate Maxima Finding of Continuous Functions under Restricted Budget - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-11-21T22:05:30+00:00","dateModified":"2021-11-21T22:05:30+00:00","description":"Carleton University Technical Report TR-95-22 November 1995 Approximate Maxima Finding of Continuous Functions under Restricted Budget Evangelos Kranakis,","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-22-approximate-maxima-finding-of-continuous-functions-under-restricted-budget\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-22-approximate-maxima-finding-of-continuous-functions-under-restricted-budget\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-22-approximate-maxima-finding-of-continuous-functions-under-restricted-budget\/#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 1995","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/"},{"@type":"ListItem","position":5,"name":"TR-95-22: Approximate Maxima Finding of Continuous Functions under Restricted Budget"}]},{"@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\/12801"}],"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=12801"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12801\/revisions"}],"predecessor-version":[{"id":12802,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12801\/revisions\/12802"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11736"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12801"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}