Algorithms for Online Advertising Portfolio Optimization and Capacitated Mobile Facility Location

Simple item page
dc.contributor.advisorRaghavan, Subramanianen_US
dc.contributor.authorSahin, Mustafaen_US
dc.contributor.departmentBusiness and Management: Decision & Information Technologiesen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2018-01-23T06:32:02Z
dc.date.available2018-01-23T06:32:02Z
dc.date.issued2017en_US
dc.description.abstractIn this dissertation, we apply large-scale optimization techniques including column generation and heuristic approaches to problems in the domains of online advertising and mobile facility location. First, we study the online advertising portfolio optimization problem (OAPOP) of an advertiser. In the OAPOP, the advertiser has a set of targeting items of interest (in the order of tens of millions for large enterprises) and a daily budget. The objective is to determine how much to bid on each targeting item to maximize the return on investment. We show the OAPOP can be represented by the Multiple Choice Knapsack Problem (MCKP). We propose an efficient column generation (CG) algorithm for the linear programming relaxation of the problem. The computations demonstrate that our CG algorithm significantly outperforms the state-of-the-art linear time algorithm used to solve the MCKP relaxation for the OAPOP. Second, we study the problem faced by the advertiser in online advertising in the presence of bid adjustments. In addition to bids, the advertisers are able to submit bid adjustments for ad query features such as geographical location, time of day, device, and audience. We introduce the Bid Adjustments Problem in Online Advertising (BAPOA) where an advertiser determines base bids and bid adjustments to maximize the return on investment. We develop an efficient algorithm to solve the BAPOA. We perform computational experiments and demonstrate, in the presence of high revenue-per-click variation across features, the revenue benefit of using bid adjustments can exceed 20%. Third, we study the capacitated mobile facility location problem (CMFLP), which is a generalization of the well-known capacitated facility location problem that has applications in supply chain and humanitarian logistics. We provide two integer programming formulations for the CMFLP. The first is on a layered graph, while the second is a set partitioning formulation. We develop a branch-and-price algorithm on the set partitioning formulation. We find that the branch-and-price procedure is particularly effective, when the ratio of the number of clients to the number of facilities is small and the facility capacities are tight. We also develop a local search heuristic and a rounding heuristic for the CMFLP.en_US
dc.identifierhttps://doi.org/10.13016/M2J09W59C
dc.identifier.urihttp://hdl.handle.net/1903/20275
dc.language.isoenen_US
dc.subject.pqcontrolledManagementen_US
dc.subject.pqcontrolledOperations researchen_US
dc.subject.pquncontrolledBranch-and-priceen_US
dc.subject.pquncontrolledColumn generationen_US
dc.subject.pquncontrolledFacility locationen_US
dc.subject.pquncontrolledInteger Programmingen_US
dc.subject.pquncontrolledLarge-scale optimizationen_US
dc.subject.pquncontrolledOnline advertisingen_US
dc.titleAlgorithms for Online Advertising Portfolio Optimization and Capacitated Mobile Facility Locationen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Sahin_umd_0117E_18383.pdf
Size:
1.71 MB
Format:
Adobe Portable Document Format
Download

Collections

UMD Theses and Dissertations
Decision, Operations & Information Technologies Theses and Dissertations