 Usage
• 71 views

# 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
Spring 2015
• Type of Item
Thesis
• Degree
Master of Science
• DOI
https://doi.org/10.7939/R3VH49