Arrow Research search

Author name cluster

Melika Abolhassani

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
2 author rows

Possible papers

2

STOC Conference 2017 Conference Paper

Beating 1-1/e for ordered prophets

  • Melika Abolhassani
  • Soheil Ehsani
  • Hossein Esfandiari
  • MohammadTaghi Hajiaghayi
  • Robert Kleinberg
  • Brendan Lucier

Hill and Kertz studied the prophet inequality on iid distributions [ The Annals of Probability 1982 ]. They proved a theoretical bound of 1 - 1/ e on the approximation factor of their algorithm. They conjectured that the best approximation factor for arbitrarily large n is 1/1+1/ e ≃ 0.731. This conjecture remained open prior to this paper for over 30 years. In this paper we present a threshold-based algorithm for the prophet inequality with n iid distributions. Using a nontrivial and novel approach we show that our algorithm is a 0.738-approximation algorithm. By beating the bound of 1/1+1/ e , this refutes the conjecture of Hill and Kertz. Moreover, we generalize our results to non-uniform distributions and discuss its applications in mechanism design.

Details

AAAI Conference 2017 Conference Paper

Market Pricing for Data Streams

  • Melika Abolhassani
  • Hossein Esfandiari
  • MohammadTaghi Hajiaghayi
  • Brendan Lucier
  • Hadi Yami

Internet-enabled marketplaces such as Amazon deal with huge datasets registering transaction of merchandises between lots of buyers and sellers. It is important that algorithms become more time and space efficient as the size of datasets increase. An algorithm that runs in polynomial time may not have a reasonable running time for such large datasets. Here, we study the development of pricing algorithms that are appropriate for use with massive datasets. We especially focus on the streaming setting, the common model for big data analysis. We present an envy-free mechanism for social welfare maximization problem in the streaming setting using O(k2 l) space, where k is the number of different goods and l is the number of available items of each good. We also provide an αapproximation mechanism for revenue maximization in this setting given an α-approximation mechanism for the corresponding offline problem exists. Moreover, we provide mechanisms to approximate the optimum social welfare (or revenue) within 1 − factor, in space independent of l which would be favorable in case l is large compared to k. Finally, we present hardness results showing approximation of optimal prices that maximize social welfare (or revenue) in the streaming setting needs Ω(l) space. We achieve our results by developing a powerful sampling technique for bipartite networks. The simplicity of our sampling technique empowers us to maintain the sample over the input sequence. Indeed, one can construct this sample in the distributed setting (a. k. a, MapReduce) and get the same results in two rounds of computations, or one may simply apply this sampling technique to provide faster offline algorithms.

PDF Details
v2026.09.13