ERA

Download the full-sized PDF of Tight Analysis of Local Search Heuristics for the Red-Blue Median ProblemDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R39W09B38

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Graduate Studies and Research, Faculty of

Collections

This file is in the following collections:

Theses and Dissertations

Tight Analysis of Local Search Heuristics for the Red-Blue Median Problem Open Access

Descriptions

Other title
Subject/Keyword
Approximation Algorithm
Red-Blue Median
Local Search
Type of item
Thesis
Degree grantor
University of Alberta
Author or creator
Zhang, Yifeng
Supervisor and department
Friggstad, Zachary (Computing Science)
Examining committee member and department
Salavatipour, Mohammad R (Computing Science)
Lin, Guohui (Computing Science)
Friggstad, Zachary (Computing Science)
Department
Department of Computing Science
Specialization

Date accepted
2017-01-31T13:22:46Z
Graduation date
2017-06:Spring 2017
Degree
Master of Science
Degree level
Master's
Abstract
Budgeted Red-Blue Median is a generalization of classic k-Median in that there are two sets of facilities, say R and B, that can be used to serve clients located in some metric space. The goal is to open kr facilities in R and kb facilities in B for some given bounds kr,kb and connect each client to their nearest open facility in a way that minimizes the total connection cost.
Language
English
DOI
doi:10.7939/R39W09B38
Rights
This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for the purpose of private, scholarly or scientific research. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
Citation for previous publication
Zachary Friggstad, Yifeng Zhang: Tight Analysis of a Multiple-Swap Heurstic for Budgeted Red-Blue Median. ICALP 2016: 75:1-75:13

File Details

Date Uploaded
Date Modified
2017-01-31T20:22:47.781+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (PDF/A)
Mime type: application/pdf
File size: 437209
Last modified: 2017:06:13 12:19:53-06:00
Filename: Zhang_Yifeng_201701_Msc.pdf
Original checksum: 5783d92671ccf430b24553baf7a33310
Activity of users you follow
User Activity Date