Let τ and σ be two polygonal curves in →., d for any fixed d. Suppose that τ and σ have n and m vertices, respectively, and m≤ n. While conditional lower bounds prevent approximating the Fréchet distance between τ and σ within a factor of 3 in strongly subquadratic time, the current best approximation algorithm attains a ratio of nc in strongly subquadratic time, for some constant cϵ(0,1). We present a randomized algorithm with running time O(nm0.99log(n/ϵ)) that approximates the Fréchet distance within a factor of 7+ϵ, with a success probability at least 1-1/n6. We also adapt our techniques to develop a randomized algorithm that approximates the discrete Fréchet distance within a factor of 7+ϵ in strongly subquadratic time. They are the first algorithms to approximate the Fréchet distance and the discrete Fréchet distance within constant factors in strongly subquadratic time.

We consider a competitive information design game in which there are multiple senders vie for the selection of a risk-neutral receiver by disclosing information about their individual state realizations. The receiver aims to select the sender who has the highest expected value of the state. We consider a general setting where the senders may be ex-ante heterogeneous, namely, while the senders' state realizations are independently distributed, they do not necessarily follow the same prior distributions. Each sender can only control the disclosure of information regarding his own state realizations, but there is no structural restriction on the set of the feasible information disclosing strategies.

In this research, we study the problem that a collector acquires items from the owner based on the item qualities the owner declares and an independent appraiser's assessments. The owner is interested in maximizing the probability that the collector acquires the items and is the only one who knows the items' factual quality. The appraiser performs her duties with impartiality, but her assessment may be subject to random noises, so it may not accurately reflect the factual quality of the items. The main challenge lies in devising mechanisms that prompt the owner to reveal accurate information, thereby optimizing the collector's expected reward. We consider the menu size of mechanisms as a measure of their practicability and study its impact on the attainable expected reward. For the single-item setting, we design optimal mechanisms with a monotone increasing menu size. Although the reward gap between the simplest and optimal mechanisms is bounded, we show that simple mechanisms with a small menu size cannot ensure any positive fraction of the optimal reward of mechanisms with a larger menu size. For the multi-item setting, we show that an ordinal mechanism that only takes the owner's ordering of the items as input is not incentive-compatible. We then propose a set of Union mechanisms that combine single-item mechanisms. Moreover, we run experiments to examine these mechanisms' robustness against the independent appraiser's assessment accuracy and the items' acquiring rate.