{"49023":{"#nid":"49023","#data":{"type":"event","title":"A Dynamic Near-Optimal Algorithm for Online Linear Programming","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETITLE:\u003C\/strong\u003E A Dynamic Near-Optimal Algorithm for Online Linear Programming\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ESPEAKER:\u003C\/strong\u003E Professor Yinyu Ye\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EABSTRACT:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EA natural optimization model that formulates many online \nresource allocation and revenue\n\u003Cbr \/\u003Emanagement problems is the online linear program (LP) where the \nconstraint matrix is revealed\n\u003Cbr \/\u003Ecolumn by column along with the objective function. We provide a \nnear-optimal algorithm for\n\u003Cbr \/\u003Ethis surprisingly general class of online problems under the \nassumption of random order of arrival\nand some mild conditions on the size of the LP right-hand-side input. \nOur learning-based algorithm works by dynamically updating a threshold price vector at \ngeometric time intervals, where\nthe dual prices learned from revealed columns in the previous period \nare used to determine the\nsequential decisions in the current period. Our algorithm has a \nfeature of learning by doing, and the prices are updated at a carefully chosen pace that is neither \ntoo fast nor too slow. In\nparticular, our algorithm doesn\u0027t assume any distribution information \non the input itself, thus\nis robust to data uncertainty and variations due to its dynamic \nlearning capability. Applications\nof our algorithm include many online multi-resource allocation and \nmulti-product revenue management\nproblems such as online routing and packing, online combinatorial \nauctions, adwords\nmatching, inventory control and yield management.\n\u003Cbr \/\u003E\n\u003Cbr \/\u003EJoint work with Shipra Agrawal and Zizhuo Wang.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"A Dynamic Near-Optimal Algorithm for Online Linear Programming","format":"limited_html"}],"field_summary_sentence":[{"value":"A Dynamic Near-Optimal Algorithm for Online Linear Programming"}],"uid":"27187","created_gmt":"2010-01-20 10:00:07","changed_gmt":"2016-10-08 01:49:32","author":"Anita Race","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2010-02-23T10:00:00-05:00","event_time_end":"2010-02-23T11:00:00-05:00","event_time_end_last":"2010-02-23T11:00:00-05:00","gmt_time_start":"2010-02-23 15:00:00","gmt_time_end":"2010-02-23 16:00:00","gmt_time_end_last":"2010-02-23 16:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"1242","name":"School of Industrial and Systems Engineering (ISYE)"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}