Data-driven Competitive Algorithms for Online Knapsack and Set Cover

The design of online algorithms has tended to focus on algorithms with worst-case guarantees, e.g., bounds on the competitive ratio. However, it is well-known that such algorithms are often overly pessimistic, performing sub-optimally on non-worst-case inputs. In this paper, we develop an approach f...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-12
Main Authors: Zeynali, Ali, Sun, Bo, Hajiesmaili, Mohammad, Wierman, Adam
Format: Article
Language:English
Subjects:
Algorithms
Electric vehicle charging
Machine learning
Optimization
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page
container_issue
container_start_page
container_title arXiv.org
container_volume
creator Zeynali, Ali
Sun, Bo
Hajiesmaili, Mohammad
Wierman, Adam
description The design of online algorithms has tended to focus on algorithms with worst-case guarantees, e.g., bounds on the competitive ratio. However, it is well-known that such algorithms are often overly pessimistic, performing sub-optimally on non-worst-case inputs. In this paper, we develop an approach for data-driven design of online algorithms that maintain near-optimal worst-case guarantees while also performing learning in order to perform well for typical inputs. Our approach is to identify policy classes that admit global worst-case guarantees, and then perform learning using historical data within the policy classes. We demonstrate the approach in the context of two classical problems, online knapsack and online set cover, proving competitive bounds for rich policy classes in each case. Additionally, we illustrate the practical implications via a case study on electric vehicle charging.
format article
fullrecord <record><control><sourceid>proquest</sourceid><recordid>TN_cdi_proquest_journals_2469447891</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2469447891</sourcerecordid><originalsourceid>FETCH-proquest_journals_24694478913</originalsourceid><addsrcrecordid>eNqNi70KwjAURoMgWLTvcME50Cbp3yitIjg46F6CvdXUNqlJ2ue3gw_g9HE451uRgHEe01wwtiGhc10URSzNWJLwgFSV9JI2Vs2ooTTDiF75BeDQP41V_jU4aI2Fq-6VRrhoOTr5eIPUDdzQL5cZ7Y6sW9k7DH-7JfvT8V6e6WjNZ0Ln685MVi-qZiIthMjyIub_VV8WyTo9</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2469447891</pqid></control><display><type>article</type><title>Data-driven Competitive Algorithms for Online Knapsack and Set Cover</title><source>Publicly Available Content Database</source><creator>Zeynali, Ali ; Sun, Bo ; Hajiesmaili, Mohammad ; Wierman, Adam</creator><creatorcontrib>Zeynali, Ali ; Sun, Bo ; Hajiesmaili, Mohammad ; Wierman, Adam</creatorcontrib><description>The design of online algorithms has tended to focus on algorithms with worst-case guarantees, e.g., bounds on the competitive ratio. However, it is well-known that such algorithms are often overly pessimistic, performing sub-optimally on non-worst-case inputs. In this paper, we develop an approach for data-driven design of online algorithms that maintain near-optimal worst-case guarantees while also performing learning in order to perform well for typical inputs. Our approach is to identify policy classes that admit global worst-case guarantees, and then perform learning using historical data within the policy classes. We demonstrate the approach in the context of two classical problems, online knapsack and online set cover, proving competitive bounds for rich policy classes in each case. Additionally, we illustrate the practical implications via a case study on electric vehicle charging.</description><identifier>EISSN: 2331-8422</identifier><language>eng</language><publisher>Ithaca: Cornell University Library, arXiv.org</publisher><subject>Algorithms ; Electric vehicle charging ; Machine learning ; Optimization</subject><ispartof>arXiv.org, 2020-12</ispartof><rights>2020. This work is published under http://arxiv.org/licenses/nonexclusive-distrib/1.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/2469447891?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>780,784,25753,37012,44590</link.rule.ids></links><search><creatorcontrib>Zeynali, Ali</creatorcontrib><creatorcontrib>Sun, Bo</creatorcontrib><creatorcontrib>Hajiesmaili, Mohammad</creatorcontrib><creatorcontrib>Wierman, Adam</creatorcontrib><title>Data-driven Competitive Algorithms for Online Knapsack and Set Cover</title><title>arXiv.org</title><description>The design of online algorithms has tended to focus on algorithms with worst-case guarantees, e.g., bounds on the competitive ratio. However, it is well-known that such algorithms are often overly pessimistic, performing sub-optimally on non-worst-case inputs. In this paper, we develop an approach for data-driven design of online algorithms that maintain near-optimal worst-case guarantees while also performing learning in order to perform well for typical inputs. Our approach is to identify policy classes that admit global worst-case guarantees, and then perform learning using historical data within the policy classes. We demonstrate the approach in the context of two classical problems, online knapsack and online set cover, proving competitive bounds for rich policy classes in each case. Additionally, we illustrate the practical implications via a case study on electric vehicle charging.</description><subject>Algorithms</subject><subject>Electric vehicle charging</subject><subject>Machine learning</subject><subject>Optimization</subject><issn>2331-8422</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2020</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><recordid>eNqNi70KwjAURoMgWLTvcME50Cbp3yitIjg46F6CvdXUNqlJ2ue3gw_g9HE451uRgHEe01wwtiGhc10URSzNWJLwgFSV9JI2Vs2ooTTDiF75BeDQP41V_jU4aI2Fq-6VRrhoOTr5eIPUDdzQL5cZ7Y6sW9k7DH-7JfvT8V6e6WjNZ0Ln685MVi-qZiIthMjyIub_VV8WyTo9</recordid><startdate>20201209</startdate><enddate>20201209</enddate><creator>Zeynali, Ali</creator><creator>Sun, Bo</creator><creator>Hajiesmaili, Mohammad</creator><creator>Wierman, Adam</creator><general>Cornell University Library, arXiv.org</general><scope>8FE</scope><scope>8FG</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>HCIFZ</scope><scope>L6V</scope><scope>M7S</scope><scope>PIMPY</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope></search><sort><creationdate>20201209</creationdate><title>Data-driven Competitive Algorithms for Online Knapsack and Set Cover</title><author>Zeynali, Ali ; Sun, Bo ; Hajiesmaili, Mohammad ; Wierman, Adam</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-proquest_journals_24694478913</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2020</creationdate><topic>Algorithms</topic><topic>Electric vehicle charging</topic><topic>Machine learning</topic><topic>Optimization</topic><toplevel>online_resources</toplevel><creatorcontrib>Zeynali, Ali</creatorcontrib><creatorcontrib>Sun, Bo</creatorcontrib><creatorcontrib>Hajiesmaili, Mohammad</creatorcontrib><creatorcontrib>Wierman, Adam</creatorcontrib><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central Korea</collection><collection>SciTech Premium Collection (Proquest) (PQ_SDU_P3)</collection><collection>ProQuest Engineering Collection</collection><collection>Engineering Database</collection><collection>Publicly Available Content Database</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering collection</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Zeynali, Ali</au><au>Sun, Bo</au><au>Hajiesmaili, Mohammad</au><au>Wierman, Adam</au><format>book</format><genre>document</genre><ristype>GEN</ristype><atitle>Data-driven Competitive Algorithms for Online Knapsack and Set Cover</atitle><jtitle>arXiv.org</jtitle><date>2020-12-09</date><risdate>2020</risdate><eissn>2331-8422</eissn><abstract>The design of online algorithms has tended to focus on algorithms with worst-case guarantees, e.g., bounds on the competitive ratio. However, it is well-known that such algorithms are often overly pessimistic, performing sub-optimally on non-worst-case inputs. In this paper, we develop an approach for data-driven design of online algorithms that maintain near-optimal worst-case guarantees while also performing learning in order to perform well for typical inputs. Our approach is to identify policy classes that admit global worst-case guarantees, and then perform learning using historical data within the policy classes. We demonstrate the approach in the context of two classical problems, online knapsack and online set cover, proving competitive bounds for rich policy classes in each case. Additionally, we illustrate the practical implications via a case study on electric vehicle charging.</abstract><cop>Ithaca</cop><pub>Cornell University Library, arXiv.org</pub><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier EISSN: 2331-8422
ispartof arXiv.org, 2020-12
issn 2331-8422
language eng
recordid cdi_proquest_journals_2469447891
source Publicly Available Content Database
subjects Algorithms
Electric vehicle charging
Machine learning
Optimization
title Data-driven Competitive Algorithms for Online Knapsack and Set Cover
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-01T11%3A28%3A03IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=document&rft.atitle=Data-driven%20Competitive%20Algorithms%20for%20Online%20Knapsack%20and%20Set%20Cover&rft.jtitle=arXiv.org&rft.au=Zeynali,%20Ali&rft.date=2020-12-09&rft.eissn=2331-8422&rft_id=info:doi/&rft_dat=%3Cproquest%3E2469447891%3C/proquest%3E%3Cgrp_id%3Ecdi_FETCH-proquest_journals_24694478913%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2469447891&rft_id=info:pmid/&rfr_iscdi=true