Source author record

Lingyi Zhang

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

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

2works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Selectable Heaps and Optimal Lazy Search Trees

We show the $O(\log n)$ time extract minimum function of efficient priority queues can be generalized to the extraction of the $k$ smallest elements in $O(k \log(n/k))$ time (we define $\log(x)$ as $\max(\log_2(x), 1)$ .), which we prove optimal for comparison-based priority queues with $o(\log n)$ time insertion. We show heap-ordered tree selection (Kaplan et al., SOSA '19) can be applied on the heap-ordered trees of the classic Fibonacci heap and Brodal queue, in $O(k \log(n/k))$ amortized and worst-case time, respectively. We additionally show the deletion of $k$ elements or selection without extraction can be performed on both heaps, also in $O(k \log(n/k))$ time. Surprisingly, all operations are possible with no modifications to the original Fibonacci heap and Brodal queue data structures. We then apply the result to lazy search trees (Sandlund & Wild, FOCS '20), creating a new interval data structure based on selectable heaps. This gives optimal $O(B+n)$ time lazy search tree performance, lowering insertion complexity into a gap $Δ_i$ from $O(\log(n/|Δ_i|) + \log \log n)$ to $O(\log(n/|Δ_i|))$ time. An $O(1)$ time merge operation is also made possible when used as a priority queue, among other situations. If Brodal queues are used, all runtimes of the lazy search tree can be made worst-case.

preprint2020arXiv

Approximation Algorithms for The Generalized Incremental Knapsack Problem

We introduce and study a discrete multi-period extension of the classical knapsack problem, dubbed generalized incremental knapsack. In this setting, we are given a set of $n$ items, each associated with a non-negative weight, and $T$ time periods with non-decreasing capacities $W_1 \leq \dots \leq W_T$ . When item $i$ is inserted at time $t$ , we gain a profit of $p_{it}$ ; however, this item remains in the knapsack for all subsequent periods. The goal is to decide if and when to insert each item, subject to the time-dependent capacity constraints, with the objective of maximizing our total profit. Interestingly, this setting subsumes as special cases a number of recently-studied incremental knapsack problems, all known to be strongly NP-hard. Our first contribution comes in the form of a polynomial-time $(\frac{1}{2}-ε)$ -approximation for the generalized incremental knapsack problem. This result is based on a reformulation as a single-machine sequencing problem, which is addressed by blending dynamic programming techniques and the classical Shmoys-Tardos algorithm for the generalized assignment problem. Combined with further enumeration-based self-reinforcing ideas and newly-revealed structural properties of nearly-optimal solutions, we turn our basic algorithm into a quasi-polynomial time approximation scheme (QPTAS). Hence, under widely believed complexity assumptions, this finding rules out the possibility that generalized incremental knapsack is APX-hard.

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.