26 citations · 42 across the 10 of their papers we have counts for
5 papers · 1 filter
Improved Algorithms for Integer Complexity
Qizheng He
The integer complexity of a positive integer is defined as the minimum number of 1's needed to represent , using additions, multiplications and parentheses. We presen…
Simple and Faster Algorithms for Knapsack
Qizheng He, Zhean Xu
In this paper, we obtain a number of new simple pseudo-polynomial time algorithms on the well-known knapsack problem, focusing on the running time dependency on the number of items…
More on Change-Making and Related Problems
Timothy M. Chan, Qizheng He
Given a set of integer-valued coin types and a target value , the well-known change-making problem asks for the minimum number of coins that sum to , assuming an unlimite…
Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing
Younan Gao, Meng He, Yakov Nekrich
Under the word RAM model, we design three data structures that can be constructed in time over points in an grid. The first data structure is an…
Further Results on Colored Range Searching
Timothy M. Chan, Qizheng He, Yakov Nekrich
We present a number of new results about range searching for colored (or "categorical") data: 1. For a set of colored points in three dimensions, we describe randomized data st…