K. V. N. Sreenivas

K. V. N. Sreenivas

Auto-generated profile, based on publicly available information

K. V. N. Sreenivas

Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India

Research Focus & Metrics

Academic Career Length

4Years (2023-Present)

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

Representative Publications

View All Publications
7 July 2023
Verified
Conference Paper
Open access
SBSiddharth Barman
Siddharth Barman
AKArindam Khan
Arindam Khan
SSSudarshan Shyam
Sudarshan Shyam
KSK. V. N. Sreenivas
K. V. N. Sreenivas
We study fair division of goods under the broad class of generalized assignment constraints. In this constraint framework, the sizes and values of the goods are agent-specific, and one needs to allocate the goods among the agents fairly while further ensuring that each agent receives a bundle of total size at most the corresponding budget of the agent. Since, in such a constraint setting, it may not always be feasible to partition all the goods among the agents, we conform---as in recent works---to the construct of charity to designate the set of unassigned goods. For this allocation framework, we obtain existential and computational guarantees for envy-free (appropriately defined) allocation of divisible and indivisible goods, respectively, among agents with individual, additive valuations for the goods. We deem allocations to be fair by evaluating envy only with respect to feasible subsets. In particular, an allocation is said to be feasibly envy-free (FEF) iff each agent prefers its bundle over every (budget) feasible subset within any other agent's bundle (and within the charity). The current work establishes that, for divisible goods, FEF allocations are guaranteed to exist and can be computed efficiently under generalized assignment constraints. Note that, in the presence of generalized assignment constraints, even the existence of such fair allocations of divisible goods is nonobvious, a priori. Our existential and computational guarantee for FEF allocations is built upon an incongruity property satisfied across a family of linear programs. This novel proof template is interesting in its own right. In the context of indivisible goods, FEF allocations do not necessarily exist, and hence, we consider the fairness notion of feasible envy-freeness up to any good (FEFx). Under this notion, an allocation of indivisible goods is declared to be fair iff for each pair of agents, a and b, envy-freeness holds for agent a against every feasible and strict subset of b's bundle; a similar guarantee is required with respect to the charity. We show that, under generalized assignment constraints, an FEFx allocation of indivisible goods always exists. In fact, our FEFx result resolves open problems posed in prior works, which provide existence guarantees under weaker fairness notions and more specialized constraints. Further, for indivisible goods and under generalized assignment constraints, we provide a pseudo-polynomial time algorithm for computing FEFx allocations, and a fully polynomial-time approximation scheme (FPTAS) for computing approximate FEFx allocations.

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]\) .