Approximation Algorithms for Single-Minded Pricing and Unique Coverage on Graphs and Geometric Objects

• Author / Creator

  Khankhajeh, Seyed Sina

• We study the Single-Minded Pricing, Unique Coverage, and Uniform-Budget Single-Minded Pricing problems on graphs and on geometric objects.

  In Single Minded Pricing, we are given a set of items and a collection of subsets of the items, called demands. For each demand, we are also given a budget. If the sum of the prices of the items in a demand is less than or equal to the budget of that demand, then the contribution of that demand to the total revenue will be the sum of the prices of the items in that demand and zero otherwise. In this problem, we want to assign prices to the items in order to maximize the total revenue. Uniform-Budget Single-Minded Pricing is a special case of Single-Minded Pricing where the budgets for all the demands are equal. In Unique Coverage, given a set of elements and a collection of subsets of the elements, we want to find a subcollection of the subsets in order to maximize the number of the elements that are uniquely covered.

  These problems can be studied in different settings, such as on graphs or on geometric objects. When studied on graphs, the items or the elements are the edges of a given graph and the demands or the subsets are paths in the graph, and when studied on geometric objects, the items or the elements are given as points on a two dimensional plane and the demands or the subset as geometric objects on the plane.

  We introduce approximation algorithms for Single-Minded Pricing, Unique Coverage, and Uniform-Budget Single-Minded Pricing on different geometric objects such as rectangles and squares and on different graphs such as trees. We also prove different hardness results for these problems.

• Subjects / Keywords

  • Single-Minded Pricing
  • Tollbooth Problem
  • Envy-Free Pricing
  • Randomized Algorithms
  • Approximation Algorithms
  • Highway Problem
  • Unique Coverage

• Graduation date

  Spring 2015

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/R3VH49

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. 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.