Rajni Dabas

Rajni Dabas

Auto-generated profile, based on publicly available information

Rajni Dabas

Department of Computer Science, University of Delhi, Delhi, India

Research Focus & Metrics

Academic Career Length

6Years (2021-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
30 April 2025 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
NANikhil Ayyadevara
Nikhil Ayyadevara
RDRajni Dabas
Rajni Dabas
AKArindam Khan
Arindam Khan
KSK. V. N. Sreenivas
K. V. N. Sreenivas
We study the online bin packing problem under two stochastic settings. In the bin packing problem, we are given n items with sizes in \((0,1]\) and the goal is to pack them into the minimum number of unit-sized bins. First, we study bin packing under the i.i.d. model, where item sizes are sampled independently and identically from a distribution in \((0,1]\) . Both the distribution and the total number of items are unknown. The items arrive one by one and their sizes are revealed upon their arrival and they must be packed immediately and irrevocably in bins of size 1. We provide a simple meta-algorithm that takes an offline \(\alpha\) -asymptotic approximation algorithm and provides a polynomial-time \((\alpha+\varepsilon)\) -competitive algorithm for online bin packing under the i.i.d. model, where \(\varepsilon > 0\) is a small constant. Using the AFPTAS for offline bin packing, we thus provide a linear time \((1+\varepsilon)\) -competitive algorithm for online bin packing under i.i.d. model, thus settling the problem. We then study the random-order model, where an adversary chooses the instance, but the order of arrival of items in the instance is drawn uniformly at random from the set of all permutations of the items. Kenyon’s seminal result (1996) showed that the Best-Fit algorithm has a competitive ratio of at most \(3/2\) in the random-order model, and conjectured the ratio to be \(\approx 1.15\) . However, it has been a long-standing open problem to break the barrier of \(3/2\) even for special cases. Recently, Albers et al. (2021) showed an improvement by proving that in the special case when all the item sizes are greater than \(1/3\) , Best-Fit has a competitive ratio of at most \(5/4\) in the random-order model. In this work, we settle this special case by showing that Best-Fit has a competitive ratio of exactly 1, i.e., Best-Fit performs almost optimally in this special case in the random-order model. We also make further progress by breaking the barrier of \(3/2\) for the 3-Partition problem, a notoriously hard special case of bin packing, where all item sizes lie in \((1/4,1/2]\) .

1 January 2022
Verified
Book Chapter
Closed access
PDF file
RDRajni Dabas
Rajni Dabas
NGNeelima Gupta
Neelima Gupta


17 July 2025 in Mathematical Programming
Verified
Journal Article
Closed access
PDF file
NGNeelima Gupta
Neelima Gupta
RDRajni Dabas
Rajni Dabas
NGNaveen Garg
Naveen Garg

21 October 2022
Verified
Book Chapter
Closed access
PDF file
RDRajni Dabas
Rajni Dabas
NGNaveen Garg
Naveen Garg
NGNeelima Gupta
Neelima Gupta
DKDilpreet Kaur
Dilpreet Kaur

8 February 2026 in Theoretical Computer Science
Verified
Journal Article
Closed access
NGNeelima Gupta
Neelima Gupta
SGSapna Grover
Sapna Grover
RDRajni Dabas
Rajni Dabas