Archive for Geometric

Multi-Attribute Profit-Maximizing Pricing

Author: Parinya Chalermsook, Khaled Elbassioni, Danupon Nanongkai, He Sun

Download: arXiv (Extended Abstract)pdf (full version)

Conference: Submitted

Journal: 

Abstract:

In the unlimited-supply profit-maximizing pricing problem, we are given the consumers’ consideration sets and know their purchase strategy (e.g. buy the cheapest items). The goal is to price the items to maximize the revenue. Previous studies suggest that this problem is too general to obtain even a sublinear approximation ratio (in terms of the number of items) even when the consumers are restricted to have very simple purchase strategies.
In this paper we initiate the study of the multi-attribute pricing problem as a direction to break this barrier. Specifically, we consider the case where each item has a constant number of attributes, and each consumer would like to buy the items that satisfy her criteria in all attributes. This notion intuitively captures typical real-world settings and has been widely-studied in marketing research, healthcare economics, etc. It also helps categorizing previously studied cases, such as highway pricing problem and graph vertex pricing problem on planar and bipartite graphs, from the general case.

We show that this notion of attributes leads to improved approximation ratios on a large class of problems. This is obtained by utilizing the fact that the consideration sets have low VC-dimension and applying Dilworth’s theorem on a certain partial order defined on the set of items. As a consequence, we present sublinear-approximation algorithms, thus breaking the previous barrier, for two well-known variants of the problem: unit-demand uniform-budget min-buying and single-minded pricing problems. Moreover, we generalize these techniques to the unit-demand utility-maximizing pricing problem and (non-uniform) unit-demand min-buying pricing problem when valuations or budgets depend on attributes, as well as the pricing problem with symmetric valuations and subadditive revenues. These results suggest that considering attributes is a promising research direction in obtaining improved approximation algorithms for such pricing problems.

Leave a Comment

Interactive Regret Minimization

Author: Danupon Nanongkai, Atish Das Sarma, Ashwin Lall, Kazuhisa Makino
(Author names are NOT in alphabetical order. )

Download: Soon

Conference: SIGMOD 2012

Journal: 

Abstract

We study the notion of regret ratio proposed by Nanongkai et al. [VLDB’10] to deal with multi-criteria decision making in database systems. The regret minimization query proposed Nanongkai et al. was shown to have features of both skyline and top-k: it does not need information from the user but still controls the output size. While this approach is suitable for obtaining a reasonably small regret ratio, it is still open whether one can make the regret ratio arbitrarily small. Moreover, it remains open whether reasonable questions can be asked to the users in order to improve efficiency of the process.

In this paper, we study the problem of minimizing regret ratio when the system is enhanced with interaction. We assume that when presented with a set of tuples, the user can tell which tuple is most preferred. Under this assumption, we develop the problem of interactive regret minimization where we fix the number of questions, and tuples per question, that we can display, and aim at minimizing the regret ratio. We try to answer two questions in this paper: (1) How much does interaction help? That is, how much can we improve the regret ratio when there are interactions? (2) How efficient can interaction be? In particular, we measure how many questions we have to ask the user in order to make her regret ratio small enough.

We answer both questions from both theoretical and practical standpoints. For the first question, we show that interaction can reduce the regret ratio almost exponentially. To do this, we prove a lower bound for the previous approach (thereby resolving an open problem from Nanongkai et al.), and develop an almost-optimal upper bound that makes the regret ratio exponentially smaller. Our experiments also confirm that, in practice, interactions help in improving the regret ratio by many orders of magnitude. For the second question, we prove that when our algorithm shows a reasonable number of points per question, it only needs a few questions to make the regret ratio small. Thus, interactive regret minimization seems to be a necessary and sufficient way to deal with multi-criteria decision making in database systems.

Leave a Comment

Representative Skylines using Threshold-based Preference Distributions

Author: Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, Richard J. Lipton, Jun Xu

Download: PDF

Conference: ICDE 2011: the IEEE International Conference on Data Engineering [link]

Abstract:

The study of skylines and their variants has receivedconsiderable attention in recent years. Skylines are essentiallysets of most interesting (undominated) tuples in a database.However, since the skyline is often very large, much researcheffort has been devoted to identifying a smaller subset of (sayk) “representative skyline” points. Several different definitionsof representative skylines have been considered. Most of theseformulations are intuitive in that they try to achieve some kindof clustering “spread” over the entire skyline, with k points. Inthis work, we take a more principled approach in defining therepresentative skyline objective. One of our main contributionsis to formulate the problem of displaying k representative skylinepoints such that the probability that a random user would clickon one of them is maximized.

Two major research questions arise naturally from this formu-lation. First, how does one mathematically model the likelihoodwith which a user is interested in and will “click” on a certaintuple? Second, how does one negotiate the absence of theknowledge of an explicit set of target users; in particular whatdo we mean by “a random user”? To answer the first question,we model users based on a novel formulation of thresholdpreferences which we will motivate further in the paper. Toanswer the second question, we assume a probability distributionof users instead of a fixed set of users. While this makes theproblem harder, it lends more mathematical structures that canbe exploited as well, as one can now work with probabilities ofthresholds and handle cumulative density functions.

On the theoretical front, our objective is NP-hard. For thecase of a finite set of users with known thresholds, we presenta simple greedy algorithm that attains an approximation ratio of (1-1/e) of the optimal. For the case of user distributions,we show that a careful yet similar greedy algorithm achieves thesame approximation ratio. Unfortunately, it turns out that thisalgorithm is rather involved and computationally expensive. Sowe present a threshold sampling based algorithm that is morecomputationally affordable and, for any fixed \epsilon > 0, has anapproximation ratio of (1-1/e-\epsilon). We perform experimentson both real and synthetic data to show that our algorithmsignificantly outperforms previously proposed approaches.

Update History

[v1] November 14, 2010 (Conference version)

Leave a Comment

Regret-Minimizing Representative Databases

Author: Danupon Nanongkai, Atish Das Sarma, Ashwin Lall, Richard J. Lipton, Jun Xu

Download: PDF

Conference: VLDB 2010: 36th International Conference on Very Large Databases [wiki]

Abstract:

We propose the k-representative regret minimization query (k-regret) as an operation to support multi-criteria decision making. Like top-k, the k-regret query assumes that users have some utility or scoring functions; however, it never asks the users to provide such functions. Like skyline, it filters out a set of interesting points from a potentially large database based on the users’ criteria; however, it never overwhelms the users by outputting too many tuples.

In particular, for any number k and any class of utility functions, the k-regret query outputs k tuples from the database and tries to minimize the {\em maximum regret ratio}. This captures how disappointed a user could be had she seen k-representative tuples instead of the whole database. We focus on the class of linear utility functions, which is widely applicable.

The first challenge of this approach is that it is not clear if the maximum regret ratio can be small, or even bounded. We answer this question affirmatively. Theoretically, we prove that the maximum regret ratio can be bounded and this bound is independent of the database size. Moreover, our extensive experiments on real and synthetic datasets suggest that in practice the maximum regret ratio is reasonably small. Additionally, algorithms developed in this paper are practical as they run in linear time in the size of the database and the experiments show that their running time is small when they run on top of the skyline operation which means that these algorithm could be integrated into current database systems.

Update History

[v1] June 28, 2010 (Conference version)

Leave a Comment