This content will become publicly available on October 31, 2024
We study the problem of approximating maximum Nash social welfare (NSW) when allocating
In this article, we extend our understanding of the
Furthermore, we show that the
 Award ID(s):
 1942321
 NSFPAR ID:
 10491728
 Publisher / Repository:
 ACM Transactions on Algorithms
 Date Published:
 Journal Name:
 ACM Transactions on Algorithms
 Volume:
 19
 Issue:
 4
 ISSN:
 15496325
 Page Range / eLocation ID:
 1 to 25
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

We study the problem of approximating maximum Nash social welfare (NSW) when allocating m indivisible items among n asymmetric agents with submodular valuations. The NSW is a wellestablished notion of fairness and efficiency, defined as the weighted geometric mean of agents' valuations. For special cases of the problem with symmetric agents and additive(like) valuation functions, approximation algorithms have been designed using approaches customized for these specific settings, and they fail to extend to more general settings. Hence, no approximation algorithm with factor independent of m is known either for asymmetric agents with additive valuations or for symmetric agents beyond additive(like) valuations. In this paper, we extend our understanding of the NSW problem to far more general settings. Our main contribution is two approximation algorithms for asymmetric agents with additive and submodular valuations respectively. Both algorithms are simple to understand and involve nontrivial modifications of a greedy repeated matchings approach. Allocations of high valued items are done separately by unmatching certain items and rematching them, by processes that are different in both algorithms. We show that these approaches achieve approximation factors of O(n) and O(n log n) for additive and submodular case respectively, which is independent of the number of items. For additive valuations, our algorithm outputs an allocation that also achieves the fairness property of envyfree up to one item (EF1). Furthermore, we show that the NSW problem under submodular valuations is strictly harder than all currently known settings with an e/(e1) factor of the hardness of approximation, even for constantly many agents. For this case, we provide a different approximation algorithm that achieves a factor of e/(e1), hence resolving it completely.more » « less

In this article, we show how a single function,
join , can be used to implement parallelbalanced binary search trees (BSTs ) simply and efficiently. Based onjoin , our approach applies to multiple balanced tree data structures, and a variety of functions for ordered sets and maps. We describe our technique as an algorithmic framework calledjoinbased algorithms . We show that thejoin function fully captures what is needed for rebalancing trees for a variety of tree algorithms, as long as the balancing scheme satisfies certain properties, which we refer to asjoinable trees. We discuss four balancing schemes that are joinable: AVL trees, redblack trees, weightbalanced trees, and treaps. We present a variety of tree algorithms that apply to joinable trees, includinginsert ,delete ,union ,intersection ,difference ,split ,range ,filter , and so on, most of them also parallel. These algorithms are generic across balancing schemes. Many algorithms are optimal in the comparison model, and we provide a general proof to show the efficiency in work for joinable trees. The algorithms are highly parallel, all with polylogarithmic span (parallel dependence). Specifically, the setset operationsunion ,intersection , anddifference have work and polylogarithmic span for input set sizes\( O(m\log (\frac{n}{m}+1)) \) and\( n \) .\( m\le n \) We implemented and tested our algorithms on the four balancing schemes. In general, all four schemes have quite similar performance, but the weightbalanced tree slightly outperforms the others. They have the same speedup characteristics, getting around 73
speedup on 72 cores (144 hyperthreads). Experimental results also show that our implementation outperforms existing parallel implementations, and our sequential version achieves close or much better performance than the sequential merging algorithm in C++ Standard Template Library (STL) on various input sizes.\( \times \) 
On hypergraphs with
m hyperedges andn vertices, wherep denotes the total size of the hyperedges, we provide the following results:We give an algorithm that runs in
time for finding a minimum\(\widetilde{O}(mn^{2k2})\) k cut in hypergraphs of arbitrary rank. This algorithm betters the previous best running time for the minimumk cut problem, fork > 2. Both of our algorithms are Monte Carlo, i.e., they return a minimumWe give an algorithm that runs in
time for finding a minimum\(\widetilde{O}(n^{\max \lbrace r,2k2\rbrace })\) k cut in hypergraphs of constant rankr . This algorithm betters the previous best running times for both the minimum cut and minimumk cut problems for dense hypergraphs.k cut (or minimum cut) with high probability. These algorithms are obtained as instantiations of a genericbranching randomized contraction technique on hypergraphs, which extends the celebrated work of Karger and Stein on recursive contractions in graphs. Our techniques and results also extend to the problems of minimum hedgecut and minimum hedgek cut on hedgegraphs, which generalize hypergraphs. 
Current computing device authentication often presents accessibility barriers for people with
upper extremity impairments (UEI) . In this article, we present a framework calledAccessible imageAssociationbased Authentication for Computing devices (A3C) , a novel recognitionbased graphical authentication framework specifically designed for people with UEI to authenticate to their computing devices. A3C requires users to provide a set of primary images the user knows that are recognizable to them and subsequently associate each primary image with a secondary image. To evaluate the efficacy of the A3C framework, we instantiated the framework by implementing a version of A3C calledA3CFA , which uses images of faces of people the user knows as the primary image and animal images as the secondary image. We then performed three studies to evaluate A3CFA: a shouldersurfing attack study (N ), a closeadversary attack study ( 319\(=\) N ), and a usability study with people with UEI ( 268\(=\) N ). We found that A3C was robust against both shouldersurfing and closeadversary attacks. We also performed a detailed study to evaluate the accessibility of A3CFA. Our participants reported that A3CFA was more usable and more secure than the authentication approaches with which they were familiar. Based on these findings, we suggest four areas of future research to further improve the design of the A3C framework. 14\(=\) 
Abstract The minimum linear ordering problem (MLOP) generalizes wellknown combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost
due to an ordering$$f(\cdot )$$ $f(\xb7)$ of the items (say [$$\sigma $$ $\sigma $n ]), i.e., , where$$\min _{\sigma } \sum _{i\in [n]} f(E_{i,\sigma })$$ ${min}_{\sigma}{\sum}_{i\in \left[n\right]}f\left({E}_{i,\sigma}\right)$ is the set of items mapped by$$E_{i,\sigma }$$ ${E}_{i,\sigma}$ to indices [$$\sigma $$ $\sigma $i ]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NPhard. We settle this question through nontrivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lovász extension of submodular functions. We show a approximation for monotone submodular MLOP where$$(2\frac{1+\ell _{f}}{1+E})$$ $(2\frac{1+{\ell}_{f}}{1+\leftE\right})$ satisfies$$\ell _{f}=\frac{f(E)}{\max _{x\in E}f(\{x\})}$$ ${\ell}_{f}=\frac{f\left(E\right)}{{max}_{x\in E}f\left(\left\{x\right\}\right)}$ . Our theory provides new approximation bounds for special cases of the problem, in particular a$$1 \le \ell _f \le E$$ $1\le {\ell}_{f}\le \leftE\right$ approximation for the matroid MLOP, where$$(2\frac{1+r(E)}{1+E})$$ $(2\frac{1+r\left(E\right)}{1+\leftE\right})$ is the rank function of a matroid. We further show that minimum latency vertex cover is$$f = r$$ $f=r$ approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest.$$\frac{4}{3}$$ $\frac{4}{3}$