4 citations · 22 across the 15 of their papers we have counts for
15 papers
Generalizations of Length Limited Huffman Coding for Hierarchical Memory Settings
Shashwat Banchhor, Rishikesh Gajjala, Yogish Sabharwal +1
In this paper, we study the problem of designing prefix-free encoding schemes having minimum average code length that can be decoded efficiently under a decode cost model that capt…
On tail estimates for Randomized Incremental Construction
Sandeep Sen
By combining several interesting applications of random sampling in geometric algorithms like point location, linear programming, segment intersections, binary space partitioning,…
On the streaming complexity of fundamental geometric problems
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra +1
In this paper, we focus on lower bounds and algorithms for some basic geometric problems in the one-pass (insertion only) streaming model. The problems considered are grouped into…
Improvable Knapsack Problems
Marc Goerigk, Yogish Sabharwal, Anita Schöbel +1
We consider a variant of the knapsack problem, where items are available with different possible weights. Using a separate budget for these item improvements, the question is: Whic…
Faster Coreset Construction for Projective Clustering via Low-Rank Approximation
Rameshwar Pratap, Sandeep Sen
In this work, we present a randomized coreset construction for projective clustering, which involves computing a set of closest -dimensional linear (affine) subspaces of a g…
Randomised Rounding with Applications
Dhiraj Madan, Sandeep Sen
We develop new techniques for rounding packing integer programs using iterative randomized rounding. It is based on a novel application of multidimensional Brownian motion in $\mat…