Source author record

Hengjie Zhang

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

ResearcherUnclaimed source record

Artificial Intelligence Computer Science and Game Theory Data Structures and Algorithms

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Tight Revenue Gaps among Multi-Unit Mechanisms

This paper considers Bayesian revenue maximization in the $k$ -unit setting, where a monopolist seller has $k$ copies of an indivisible item and faces $n$ unit-demand buyers (whose value distributions can be non-identical). Four basic mechanisms among others have been widely employed in practice and widely studied in the literature: {\sf Myerson Auction}, {\sf Sequential Posted-Pricing}, {\sf $(k + 1)$ -th Price Auction with Anonymous Reserve}, and {\sf Anonymous Pricing}. Regarding a pair of mechanisms, we investigate the largest possible ratio between the two revenues (a.k.a.\ the revenue gap), over all possible value distributions of the buyers. Divide these four mechanisms into two groups: (i)~the discriminating mechanism group, {\sf Myerson Auction} and {\sf Sequential Posted-Pricing}, and (ii)~the anonymous mechanism group, {\sf Anonymous Reserve} and {\sf Anonymous Pricing}. Within one group, the involved two mechanisms have an asymptotically tight revenue gap of $1 + Θ(1 / \sqrt{k})$ . In contrast, any two mechanisms from the different groups have an asymptotically tight revenue gap of $Θ(\log k)$ .

preprint2020arXiv

Distributed Linguistic Representations in Decision Making: Taxonomy, Key Elements and Applications, and Challenges in Data Science and Explainable Artificial Intelligence

Distributed linguistic representations are powerful tools for modelling the uncertainty and complexity of preference information in linguistic decision making. To provide a comprehensive perspective on the development of distributed linguistic representations in decision making, we present the taxonomy of existing distributed linguistic representations. Then, we review the key elements of distributed linguistic information processing in decision making, including the distance measurement, aggregation methods, distributed linguistic preference relations, and distributed linguistic multiple attribute decision making models. Next, we provide a discussion on ongoing challenges and future research directions from the perspective of data science and explainable artificial intelligence.

preprint2020arXiv

Faster Dynamic Matrix Inverse for Faster LPs

Motivated by recent Linear Programming solvers, we design dynamic data structures for maintaining the inverse of an $n\times n$ real matrix under $\textit{low-rank}$ updates, with polynomially faster amortized running time. Our data structure is based on a recursive application of the Woodbury-Morrison identity for implementing $\textit{cascading}$ low-rank updates, combined with recent sketching technology. Our techniques and amortized analysis of multi-level partial updates, may be of broader interest to dynamic matrix problems. This data structure leads to the fastest known LP solver for general (dense) linear programs, improving the running time of the recent algorithms of (Cohen et al.'19, Lee et al.'19, Brand'20) from $O^*(n^{2+ \max\{\frac{1}{6}, ω-2, \frac{1-α}{2}\}})$ to $O^*(n^{2+\max\{\frac{1}{18}, ω-2, \frac{1-α}{2}\}})$ , where $ω$ and $α$ are the fast matrix multiplication exponent and its dual. Hence, under the common belief that $ω\approx 2$ and $α\approx 1$ , our LP solver runs in $O^*(n^{2.055})$ time instead of $O^*(n^{2.16})$ .

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.