We introduce and study the weighted version of an online matching problem in the Euclidean plane with non-crossing constraints: points with non-negative weights arrive online, and an algorithm can match an arriving point to one of the unmatched previously arrived points. In the classic model, the decision on how to match (if at all) a newly arriving point is irrevocable. The goal is to maximize the total weight of matched points under the constraint that straight-line segments corresponding to the edges of the matching do not intersect. The unweighted version of the problem was introduced in the offline setting by Atallah in 1985, and this problem became a subject of study in the online setting with and without advice in several recent papers. We observe that deterministic online algorithms cannot guarantee a non-trivial competitive ratio for the weighted problem, but we give upper and lower bounds on the problem with bounded weights. In contrast to the deterministic case, we show that using randomization, a constant competitive ratio is possible for arbitrary weights. We also study other variants of the problem, including revocability and collinear points, both of which permit non-trivial online algorithms, and we give upper and lower bounds for the attainable competitive ratios. Finally, we prove an advice complexity bound for obtaining optimality, improving the best known bound.

This paper studies the online vector bin packing (OVBP) problem and the related problem of online hypergraph coloring (OHC). Firstly, we use a double counting argument to prove an upper bound on the competitive ratio of FirstFit for OVBP. Our proof is conceptually simple, and strengthens the result in [1] by removing the dependency on the bin size parameter. Secondly, we introduce a notion of an online incidence matrix that is defined for every instance of OHC. Using this notion, we provide a reduction from OHC to OVBP, which allows us to carry known lower bounds on the competitive ratio of algorithms from OHC to OVBP. Our approach significantly simplifies the previous argument from [1] that relied on using intricate graph structures. In addition, we slightly improve their lower bounds. Lastly, we establish a tight bound on the competitive ratio of algorithms for OHC, where input is restricted to be a hypertree, thus resolving a conjecture in [2]. The crux of this proof lies in solving a certain combinatorial partition problem about multi-family of subsets, which might be of independent interest.

The information complexity of a function $f$ is the minimum amount of information Alice and Bob need to exchange to compute the function $f$. In this paper we provide an algorithm for approximating the information complexity of an arbitrary function $f$ to within any additive error $α> 0$, thus resolving an open question as to whether information complexity is computable. In the process, we give the first explicit upper bound on the rate of convergence of the information complexity of $f$ when restricted to $b$-bit protocols to the (unrestricted) information complexity of $f$.