Source author record

Chinmay Karande

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computer Science and Game Theory

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2010arXiv

Market Equilibrium with Transaction Costs

Identical products being sold at different prices in different locations is a common phenomenon. Price differences might occur due to various reasons such as shipping costs, trade restrictions and price discrimination. To model such scenarios, we supplement the classical Fisher model of a market by introducing {\em transaction costs}. For every buyer $i$ and every good $j$ , there is a transaction cost of $\cij$; if the price of good $j$ is $p_j$ , then the cost to the buyer $i$ {\em per unit} of $j$ is $p_j + \cij$. This allows the same good to be sold at different (effective) prices to different buyers. We provide a combinatorial algorithm that computes $ε$ -approximate equilibrium prices and allocations in $O\left(\frac{1}ε(n+\log{m})mn\log(B/ε)\right)$ operations - where $m$ is the number goods, $n$ is the number of buyers and $B$ is the sum of the budgets of all the buyers.

preprint2010arXiv

Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocations

We study the following vertex-weighted online bipartite matching problem: $G(U, V, E)$ is a bipartite graph. The vertices in $U$ have weights and are known ahead of time, while the vertices in $V$ arrive online in an arbitrary order and have to be matched upon arrival. The goal is to maximize the sum of weights of the matched vertices in $U$ . When all the weights are equal, this reduces to the classic \emph{online bipartite matching} problem for which Karp, Vazirani and Vazirani gave an optimal $\left(1-\frac{1}{e}\right)$ -competitive algorithm in their seminal work~\cite{KVV90}. Our main result is an optimal $\left(1-\frac{1}{e}\right)$ -competitive randomized algorithm for general vertex weights. We use \emph{random perturbations} of weights by appropriately chosen multiplicative factors. Our solution constitutes the first known generalization of the algorithm in~\cite{KVV90} in this model and provides new insights into the role of randomization in online allocation problems. It also effectively solves the problem of \emph{online budgeted allocations} \cite{MSVV05} in the case when an agent makes the same bid for any desired item, even if the bid is comparable to his budget - complementing the results of \cite{MSVV05, BJN07} which apply when the bids are much smaller than the budgets.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.