Arindam Khan
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Arindam Khan has a total of 50 co-authors. Here are the top co-authors by number of shared publications:
- Andreas Wiese
Technical University of Munich, Munich, Germany
5 shared publications K. V. N. Sreenivas
Indian Institute of Science Bengaluru India
5 shared publications- Klaus Jansen
Kiel University
4 shared publications - Siddharth Barman
Indian Institute of Science Bangalore
4 shared publications - Waldo Gálvez
Universidad de Concepción, Chile
3 shared publications - Aditya Subramanian
Indian Institute of Science Bengaluru
2 shared publications
Latest Publications
- Open Access
- 2 July 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (4) , 1-31
A \((2+\varepsilon)\) -Approximation Algorithm for Maximum Independent Set of RectanglesWe study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overlapping rectangles of maximum cardinality. In a recent breakthrough, Mitchell [53] obtained the first constant-factor approximation algorithm for MISR. His algorithm achieves an approximation ratio of 10 and it is based on a dynamic program that intuitively recursively partitions the input plane into special polygons called corner-clipped rectangles (CCRs) , without intersecting certain special horizontal line segments called fences . In this paper, we present a \((2+\varepsilon)\) -approximation algorithm for MISR, which is also based on a recursive partitioning scheme. First, we use a partition into a class of axis-parallel polygons with constant complexity each that are more general than CCRs. This allows us to provide an arguably simpler analysis and, at the same time, already improves the approximation ratio to 4. Then, using a more elaborate charging scheme and a recursive partitioning into general axis-parallel polygons with constant complexity, we improve our approximation ratio to \(2+\varepsilon\) . In particular, we construct a recursive partitioning based on more general fences which can be sequences of up to \(O(1/\varepsilon)\) line segments each. This partitioning routine and our other new ideas may be useful for future work towards a PTAS for MISR.- 2 July 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (4) , 1-31
Open AccessA \((2+\varepsilon)\) -Approximation Algorithm for Maximum Independent Set of RectanglesWe study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overlapping rectangles of maximum cardinality. In a recent breakthrough, Mitchell [53] obtained the first constant-factor approximation algorithm for MISR. His algorithm achieves an approximation ratio of 10 and it is based on a dynamic program that intuitively recursively partitions the input plane into special polygons called corner-clipped rectangles (CCRs) , without intersecting certain special horizontal line segments called fences . In this paper, we present a \((2+\varepsilon)\) -approximation algorithm for MISR, which is also based on a recursive partitioning scheme. First, we use a partition into a class of axis-parallel polygons with constant complexity each that are more general than CCRs. This allows us to provide an arguably simpler analysis and, at the same time, already improves the approximation ratio to 4. Then, using a more elaborate charging scheme and a recursive partitioning into general axis-parallel polygons with constant complexity, we improve our approximation ratio to \(2+\varepsilon\) . In particular, we construct a recursive partitioning based on more general fences which can be sequences of up to \(O(1/\varepsilon)\) line segments each. This partitioning routine and our other new ideas may be useful for future work towards a PTAS for MISR. - Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1145-1156
Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
We study the two-dimensional (geometric) knapsack problem with rotations (2DKR), in which we are given a square knapsack and a set of rectangles with associated profits. The objective is to find a maximum profit subset of rectangles that can be packed without overlap in an axis-aligned manner, possibly by rotating some rectangles by 90∘. The best-known polynomial time algorithm for the problem has an approximation ratio of 3/2+є for any constant є>0, with an improvement to 4/3+є in the cardinality case, due to Gálvez, Grandoni, Heydrich, Ingala, Khan, and Wiese (FOCS 2017, TALG 2021). Obtaining a PTAS for the problem, even in the cardinality case, has remained a major open question in the setting of multidimensional packing problems, as mentioned in the survey by Christensen, Khan, Tetali, and Pokutta (Computer Science Review, 2017). In this paper, we present a PTAS for the cardinality case of 2DKR. In contrast to the setting without rotations, we show that there are (1+є)-approximate solutions in which all items are packed greedily inside a constant number of rectangular containers. Our result is based on a new resource contraction lemma, which might be of independent interest. With our techniques, we also obtain a (1+є)-approximation algorithm in the weighted case when all given items are skewed, i.e., each of them has sufficiently small height or sufficiently small width. In contrast, for the general weighted case, we prove that this simple type of packing is not sufficient to obtain a better approximation ratio than 1.5. However, we break this structural barrier and design a (1.497+є)-approximation algorithm for 2DKR in the weighted case. Our arguments also improve the best-known approximation ratio for the (weighted) case without rotations to 13/7+є ≈ 1.857+є. Finally, we establish a lower bound of nΩ(1/є) on the running time of any (1+є)-approximation algorithm for our problem with or without rotations – even in the cardinality setting, assuming the k-Sum Conjecture. In particular, this shows that an approximation scheme for the case of rectangles of two-dimensional geometric knapsack requires much more running time than for the case of squares.
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1145-1156
Open AccessApproximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
We study the two-dimensional (geometric) knapsack problem with rotations (2DKR), in which we are given a square knapsack and a set of rectangles with associated profits. The objective is to find a maximum profit subset of rectangles that can be packed without overlap in an axis-aligned manner, possibly by rotating some rectangles by 90∘. The best-known polynomial time algorithm for the problem has an approximation ratio of 3/2+є for any constant є>0, with an improvement to 4/3+є in the cardinality case, due to Gálvez, Grandoni, Heydrich, Ingala, Khan, and Wiese (FOCS 2017, TALG 2021). Obtaining a PTAS for the problem, even in the cardinality case, has remained a major open question in the setting of multidimensional packing problems, as mentioned in the survey by Christensen, Khan, Tetali, and Pokutta (Computer Science Review, 2017). In this paper, we present a PTAS for the cardinality case of 2DKR. In contrast to the setting without rotations, we show that there are (1+є)-approximate solutions in which all items are packed greedily inside a constant number of rectangular containers. Our result is based on a new resource contraction lemma, which might be of independent interest. With our techniques, we also obtain a (1+є)-approximation algorithm in the weighted case when all given items are skewed, i.e., each of them has sufficiently small height or sufficiently small width. In contrast, for the general weighted case, we prove that this simple type of packing is not sufficient to obtain a better approximation ratio than 1.5. However, we break this structural barrier and design a (1.497+є)-approximation algorithm for 2DKR in the weighted case. Our arguments also improve the best-known approximation ratio for the (weighted) case without rotations to 13/7+є ≈ 1.857+є. Finally, we establish a lower bound of nΩ(1/є) on the running time of any (1+є)-approximation algorithm for our problem with or without rotations – even in the cardinality setting, assuming the k-Sum Conjecture. In particular, this shows that an approximation scheme for the case of rectangles of two-dimensional geometric knapsack requires much more running time than for the case of squares.
- Open Access
Ads that Stick: Near-Optimal Ad Optimization through Psychological Behavior Models
Optimizing the timing and frequency of ads is a central problem in digital advertising, with significant economic consequences. Existing scheduling policies rely on simple heuristics, such as uniform spacing and frequency caps, that overlook long-term user interest. However, it is well-known that users' long-term interest and engagement result from the interplay of several psychological effects (Curmei, Haupt, Recht, Hadfield-Menell, ACM CRS, 2022). In this work, we model change in user interest upon showing ads based on three key psychological principles: mere exposure, hedonic adaptation, and operant conditioning. The first two effects are modeled using a concave function of user interest with repeated exposure, while the third effect is modeled using a temporal decay function, which explains the decline in user interest due to overexposure. Under our psychological behavior model, we ask the following question: Given a continuous time interval $T$, how many ads should be shown, and at what times, to maximize the user interest towards the ads? Towards answering this question, we first show that, if the number of displayed ads is fixed, then the optimal ad-schedule only depends on the operant conditioning function. Our main result is a quasi-linear time algorithm that outputs a near-optimal ad-schedule, i.e., the difference in the performance of our schedule and the optimal schedule is exponentially small. Our algorithm leads to significant insights about optimal ad placement and shows that simple heuristics such as uniform spacing are sub-optimal under many natural settings. The optimal number of ads to display, which also depends on the mere exposure and hedonistic adaptation functions, can be found through a simple linear search given the above algorithm. We further support our findings with experimental results, demonstrating that our strategy outperforms various baselines.Open AccessAds that Stick: Near-Optimal Ad Optimization through Psychological Behavior Models
Optimizing the timing and frequency of ads is a central problem in digital advertising, with significant economic consequences. Existing scheduling policies rely on simple heuristics, such as uniform spacing and frequency caps, that overlook long-term user interest. However, it is well-known that users' long-term interest and engagement result from the interplay of several psychological effects (Curmei, Haupt, Recht, Hadfield-Menell, ACM CRS, 2022). In this work, we model change in user interest upon showing ads based on three key psychological principles: mere exposure, hedonic adaptation, and operant conditioning. The first two effects are modeled using a concave function of user interest with repeated exposure, while the third effect is modeled using a temporal decay function, which explains the decline in user interest due to overexposure. Under our psychological behavior model, we ask the following question: Given a continuous time interval $T$, how many ads should be shown, and at what times, to maximize the user interest towards the ads? Towards answering this question, we first show that, if the number of displayed ads is fixed, then the optimal ad-schedule only depends on the operant conditioning function. Our main result is a quasi-linear time algorithm that outputs a near-optimal ad-schedule, i.e., the difference in the performance of our schedule and the optimal schedule is exponentially small. Our algorithm leads to significant insights about optimal ad placement and shows that simple heuristics such as uniform spacing are sub-optimal under many natural settings. The optimal number of ads to display, which also depends on the mere exposure and hedonistic adaptation functions, can be found through a simple linear search given the above algorithm. We further support our findings with experimental results, demonstrating that our strategy outperforms various baselines. - Open Access
- 22 May 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
Tight Approximation Algorithms for Two-dimensional Guillotine Strip Packing
In the Strip Packing problem (SP), we are given a vertical half-strip \([0,W]\times[0,\infty)\) and a set of \(n\) axis-aligned rectangles of width at most \(W\) . The goal is to find a non-overlapping packing of all rectangles into the strip such that the height of the packing is minimized. A well-studied and frequently used practical constraint is to allow only those packings that are guillotine separable, i.e., every rectangle in the packing can be obtained by recursively applying a sequence of edge-to-edge axis-parallel cuts (guillotine cuts) that do not intersect any item of the solution. In this paper, we study approximation algorithms for the Guillotine Strip Packing problem (GSP), i.e., the Strip Packing problem where we require additionally that the packing needs to be guillotine separable. This problem generalizes the classical Bin Packing problem and also makespan minimization on identical machines, and thus it is already strongly \(\mathsf{NP}\) -hard. Moreover, due to a reduction from the Partition problem, it is \(\mathsf{NP}\) -hard to obtain a polynomial-time \((3/2-\varepsilon)\) -approximation algorithm for GSP for any \(\varepsilon>0\) (exactly as Strip Packing ). We provide a matching polynomial time \((3/2+\varepsilon)\) -approximation algorithm for GSP. Furthermore, we present a pseudo-polynomial time \((1+\varepsilon)\) -approximation algorithm for GSP. This is surprising as it is \(\mathsf{NP}\) -hard to obtain a \((5/4-\varepsilon)\) -approximation algorithm for (general) Strip Packing in pseudo-polynomial time. Thus, our results essentially settle the approximability of GSP for both the polynomial and the pseudo-polynomial settings.- 22 May 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
Open AccessTight Approximation Algorithms for Two-dimensional Guillotine Strip Packing
In the Strip Packing problem (SP), we are given a vertical half-strip \([0,W]\times[0,\infty)\) and a set of \(n\) axis-aligned rectangles of width at most \(W\) . The goal is to find a non-overlapping packing of all rectangles into the strip such that the height of the packing is minimized. A well-studied and frequently used practical constraint is to allow only those packings that are guillotine separable, i.e., every rectangle in the packing can be obtained by recursively applying a sequence of edge-to-edge axis-parallel cuts (guillotine cuts) that do not intersect any item of the solution. In this paper, we study approximation algorithms for the Guillotine Strip Packing problem (GSP), i.e., the Strip Packing problem where we require additionally that the packing needs to be guillotine separable. This problem generalizes the classical Bin Packing problem and also makespan minimization on identical machines, and thus it is already strongly \(\mathsf{NP}\) -hard. Moreover, due to a reduction from the Partition problem, it is \(\mathsf{NP}\) -hard to obtain a polynomial-time \((3/2-\varepsilon)\) -approximation algorithm for GSP for any \(\varepsilon>0\) (exactly as Strip Packing ). We provide a matching polynomial time \((3/2+\varepsilon)\) -approximation algorithm for GSP. Furthermore, we present a pseudo-polynomial time \((1+\varepsilon)\) -approximation algorithm for GSP. This is surprising as it is \(\mathsf{NP}\) -hard to obtain a \((5/4-\varepsilon)\) -approximation algorithm for (general) Strip Packing in pseudo-polynomial time. Thus, our results essentially settle the approximability of GSP for both the polynomial and the pseudo-polynomial settings. - Open Access
- 30 April 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (2) , 1-39
Near-optimal Algorithms for Stochastic Online Bin Packing
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]\) .- 30 April 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 21 (2) , 1-39
Open AccessNear-optimal Algorithms for Stochastic Online Bin Packing
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]\) . - Open Access
Improved Approximation Algorithms for Three-Dimensional Knapsack
We study the three-dimensional Knapsack (3DK) problem, in which we are given a set of axis-aligned cuboids with associated profits and an axis-aligned cube knapsack. The objective is to find a non-overlapping axis-aligned packing (by translation) of the maximum profit subset of cuboids into the cube. The previous best approximation algorithm is due to Diedrich, Harren, Jansen, Thöle, and Thomas (2008), who gave a $(7+\varepsilon)$-approximation algorithm for 3DK and a $(5+\varepsilon)$-approximation algorithm for the variant when the items can be rotated by 90 degrees around any axis, for any constant $\varepsilon>0$. Chlebík and Chlebíková (2009) showed that the problem does not admit an asymptotic polynomial-time approximation scheme. We provide an improved polynomial-time $(139/29+\varepsilon) \approx 4.794$-approximation algorithm for 3DK and $(30/7+\varepsilon) \approx 4.286$-approximation when rotations by 90 degrees are allowed. We also provide improved approximation algorithms for several variants such as the cardinality case (when all items have the same profit) and uniform profit-density case (when the profit of an item is equal to its volume). Our key technical contribution is container packing -- a structured packing in 3D such that all items are assigned into a constant number of containers, and each container is packed using a specific strategy based on its type. We first show the existence of highly profitable container packings. Thereafter, we show that one can find near-optimal container packing efficiently using a variant of the Generalized Assignment Problem (GAP).Open AccessImproved Approximation Algorithms for Three-Dimensional Knapsack
We study the three-dimensional Knapsack (3DK) problem, in which we are given a set of axis-aligned cuboids with associated profits and an axis-aligned cube knapsack. The objective is to find a non-overlapping axis-aligned packing (by translation) of the maximum profit subset of cuboids into the cube. The previous best approximation algorithm is due to Diedrich, Harren, Jansen, Thöle, and Thomas (2008), who gave a $(7+\varepsilon)$-approximation algorithm for 3DK and a $(5+\varepsilon)$-approximation algorithm for the variant when the items can be rotated by 90 degrees around any axis, for any constant $\varepsilon>0$. Chlebík and Chlebíková (2009) showed that the problem does not admit an asymptotic polynomial-time approximation scheme. We provide an improved polynomial-time $(139/29+\varepsilon) \approx 4.794$-approximation algorithm for 3DK and $(30/7+\varepsilon) \approx 4.286$-approximation when rotations by 90 degrees are allowed. We also provide improved approximation algorithms for several variants such as the cardinality case (when all items have the same profit) and uniform profit-density case (when the profit of an item is equal to its volume). Our key technical contribution is container packing -- a structured packing in 3D such that all items are assigned into a constant number of containers, and each container is packed using a specific strategy based on its type. We first show the existence of highly profitable container packings. Thereafter, we show that one can find near-optimal container packing efficiently using a variant of the Generalized Assignment Problem (GAP). - 13 June 2024
- Published by Springer Nature in Mathematical Programming
- Vol. 206 (1-2) , 607-630
A PTAS for the horizontal rectangle stabbing problem
- 13 June 2024
- Published by Springer Nature in Mathematical Programming
- Vol. 206 (1-2) , 607-630
A PTAS for the horizontal rectangle stabbing problem
- Open Access
Bin Packing under Random-Order: Breaking the Barrier of 3/2
Best-Fit is one of the most prominent and practically used algorithms for the bin packing problem, where a set of items with associated sizes needs to be packed in the minimum number of unit-capacity bins. Kenyon [SODA '96] studied online bin packing under random-order arrival, where the adversary chooses the list of items, but the items arrive one by one according to an arrival order drawn uniformly randomly from the set of all permutations of the items. Kenyon's seminal result established an upper bound of $1.5$ and a lower bound of $1.08$ on the random-order ratio of Best-Fit, and it was conjectured that the true ratio is $\approx 1.15$. The conjecture, if true, will also imply that Best-Fit (on randomly permuted input) has the best performance guarantee among all the widely-used simple algorithms for (offline) bin packing. This conjecture has remained one of the major open problems in the area, as highlighted in the recent survey on random-order models by Gupta and Singla [Beyond the Worst-Case Analysis of Algorithms '20]. Recently, Albers et al. [Algorithmica '21] improved the upper bound to $1.25$ for the special case when all the item sizes are greater than $1/3$, and they improve the lower bound to $1.1$. Ayyadevara et al. [ICALP '22] obtained an improved result for the special case when all the item sizes lie in $(1/4, 1/2]$, which corresponds to the $3$-partition problem. The upper bound of $3/2$ for the general case, however, has remained unimproved. In this paper, we make the first progress towards the conjecture, by showing that Best-Fit achieves a random-order ratio of at most $1.5 - \varepsilon$, for a small constant $\varepsilon>0$. Furthermore, we establish an improved lower bound of $1.144$ on the random-order ratio of Best-Fit, nearly reaching the conjectured ratio.Open AccessBin Packing under Random-Order: Breaking the Barrier of 3/2
Best-Fit is one of the most prominent and practically used algorithms for the bin packing problem, where a set of items with associated sizes needs to be packed in the minimum number of unit-capacity bins. Kenyon [SODA '96] studied online bin packing under random-order arrival, where the adversary chooses the list of items, but the items arrive one by one according to an arrival order drawn uniformly randomly from the set of all permutations of the items. Kenyon's seminal result established an upper bound of $1.5$ and a lower bound of $1.08$ on the random-order ratio of Best-Fit, and it was conjectured that the true ratio is $\approx 1.15$. The conjecture, if true, will also imply that Best-Fit (on randomly permuted input) has the best performance guarantee among all the widely-used simple algorithms for (offline) bin packing. This conjecture has remained one of the major open problems in the area, as highlighted in the recent survey on random-order models by Gupta and Singla [Beyond the Worst-Case Analysis of Algorithms '20]. Recently, Albers et al. [Algorithmica '21] improved the upper bound to $1.25$ for the special case when all the item sizes are greater than $1/3$, and they improve the lower bound to $1.1$. Ayyadevara et al. [ICALP '22] obtained an improved result for the special case when all the item sizes lie in $(1/4, 1/2]$, which corresponds to the $3$-partition problem. The upper bound of $3/2$ for the general case, however, has remained unimproved. In this paper, we make the first progress towards the conjecture, by showing that Best-Fit achieves a random-order ratio of at most $1.5 - \varepsilon$, for a small constant $\varepsilon>0$. Furthermore, we establish an improved lower bound of $1.144$ on the random-order ratio of Best-Fit, nearly reaching the conjectured ratio. - Open Access
- 1 August 2023
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 4, 4100-4108
Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits
We study the Improving Multi-Armed Bandit problem, where the reward obtained from an arm increases with the number of pulls it receives. This model provides an elegant abstraction for many real-world problems in domains such as education and employment, where decisions about the distribution of opportunities can affect the future capabilities of communities and the disparity between them. A decision-maker in such settings must consider the impact of her decisions on future rewards in addition to the standard objective of maximizing her cumulative reward at any time. We study the tension between two seemingly conflicting objectives in the horizon-unaware setting: a) maximizing the cumulative reward at any time and b) ensuring that arms with better long-term rewards get sufficient pulls even if they initially have low rewards. We show that, surprisingly, the two objectives are aligned with each other. Our main contribution is an anytime algorithm for the IMAB problem that achieves the best possible cumulative reward while ensuring that the arms reach their true potential given sufficient time. Our algorithm mitigates the initial disparity due to lack of opportunity and continues pulling an arm until it stops improving. We prove the optimality of our algorithm by showing that a) any algorithm for the IMAB problem, no matter how utilitarian, must suffer Omega(T) policy regret and Omega(k) competitive ratio with respect to the optimal offline policy, and b) the competitive ratio of our algorithm is O(k).
- 1 August 2023
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 4, 4100-4108
Open AccessMitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits
We study the Improving Multi-Armed Bandit problem, where the reward obtained from an arm increases with the number of pulls it receives. This model provides an elegant abstraction for many real-world problems in domains such as education and employment, where decisions about the distribution of opportunities can affect the future capabilities of communities and the disparity between them. A decision-maker in such settings must consider the impact of her decisions on future rewards in addition to the standard objective of maximizing her cumulative reward at any time. We study the tension between two seemingly conflicting objectives in the horizon-unaware setting: a) maximizing the cumulative reward at any time and b) ensuring that arms with better long-term rewards get sufficient pulls even if they initially have low rewards. We show that, surprisingly, the two objectives are aligned with each other. Our main contribution is an anytime algorithm for the IMAB problem that achieves the best possible cumulative reward while ensuring that the arms reach their true potential given sufficient time. Our algorithm mitigates the initial disparity due to lack of opportunity and continues pulling an arm until it stops improving. We prove the optimality of our algorithm by showing that a) any algorithm for the IMAB problem, no matter how utilitarian, must suffer Omega(T) policy regret and Omega(k) competitive ratio with respect to the optimal offline policy, and b) the competitive ratio of our algorithm is O(k).
- Open Access
- 27 July 2023
- Published by Springer Nature in Algorithmica
- Vol. 85 (12) , 3649-3679
Peak Demand Minimization via Sliced Strip Packing
We study the Non-preemptive Peak Demand Minimization (NPDM) problem, where we are given a set of jobs, specified by their processing times and energy requirements. The goal is to schedule all jobs within a fixed time period such that the peak load (the maximum total energy requirement at any time) is minimized. This problem has recently received significant attention due to its relevance in smart-grids. Theoretically, the problem is related to the classical strip packing problem (SP). In SP, a given set of axis-aligned rectangles must be packed into a fixed-width strip, such that the height of the strip is minimized. NPDM can be modeled as strip packing with slicing and stacking constraint: each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The stacking constraint forbids solutions where two slices of the same rectangle are intersected by the same vertical line. Non-preemption enforces the slices to be placed in contiguous horizontal locations (but may be placed at different vertical locations). We obtain a $$(5/3+\varepsilon )$$ -approximation algorithm for the problem. We also provide an asymptotic efficient polynomial-time approximation scheme (AEPTAS) which generates a schedule for almost all jobs with energy consumption $$(1+\varepsilon ) {\textrm{OPT}}$$ . The remaining jobs fit into a thin container of height 1. This AEPTAS is used as a subroutine to acquire the $$(5/3+\varepsilon )$$ -approximation algorithm. The previous best result for NPDM was a 2.7-approximation based on FFDH (Ranjan et al., in: 2015 IEEE symposium on computers and communication (ISCC), pp 758–763, IEEE, 2015). One of our key ideas is providing several new lower bounds on the optimal solution of a geometric packing, which could be useful in other related problems. These lower bounds help us to obtain approximative solutions based on Steinberg’s algorithm in many cases. In addition, we show how to split schedules generated by the AEPTAS into few segments and to rearrange the corresponding jobs to insert the thin container mentioned above, such that it does not exceed the bound of $$(5/3+\varepsilon ) {\textrm{OPT}}$$ .- 27 July 2023
- Published by Springer Nature in Algorithmica
- Vol. 85 (12) , 3649-3679
Open AccessPeak Demand Minimization via Sliced Strip Packing
We study the Non-preemptive Peak Demand Minimization (NPDM) problem, where we are given a set of jobs, specified by their processing times and energy requirements. The goal is to schedule all jobs within a fixed time period such that the peak load (the maximum total energy requirement at any time) is minimized. This problem has recently received significant attention due to its relevance in smart-grids. Theoretically, the problem is related to the classical strip packing problem (SP). In SP, a given set of axis-aligned rectangles must be packed into a fixed-width strip, such that the height of the strip is minimized. NPDM can be modeled as strip packing with slicing and stacking constraint: each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The stacking constraint forbids solutions where two slices of the same rectangle are intersected by the same vertical line. Non-preemption enforces the slices to be placed in contiguous horizontal locations (but may be placed at different vertical locations). We obtain a $$(5/3+\varepsilon )$$ -approximation algorithm for the problem. We also provide an asymptotic efficient polynomial-time approximation scheme (AEPTAS) which generates a schedule for almost all jobs with energy consumption $$(1+\varepsilon ) {\textrm{OPT}}$$ . The remaining jobs fit into a thin container of height 1. This AEPTAS is used as a subroutine to acquire the $$(5/3+\varepsilon )$$ -approximation algorithm. The previous best result for NPDM was a 2.7-approximation based on FFDH (Ranjan et al., in: 2015 IEEE symposium on computers and communication (ISCC), pp 758–763, IEEE, 2015). One of our key ideas is providing several new lower bounds on the optimal solution of a geometric packing, which could be useful in other related problems. These lower bounds help us to obtain approximative solutions based on Steinberg’s algorithm in many cases. In addition, we show how to split schedules generated by the AEPTAS into few segments and to rearrange the corresponding jobs to insert the thin container mentioned above, such that it does not exceed the bound of $$(5/3+\varepsilon ) {\textrm{OPT}}$$ .