(As in the convention in theoretical computer science, unless stated otherwise the author names are listed alphabetically)

Thesis/ Survey/ Book Articles

Abstract: The bin packing problem has been the corner stone of approximation algorithms and has been extensively studied starting from the early seventies. In the
classical bin packing problem, we are given a list of real numbers in the range (0, 1],
the goal is to place them in a minimum number of bins so that no bin holds numbers summing to more than 1. In this thesis we study approximation algorithms for
three generalizations of bin packing: geometric bin packing, vector bin packing and
weighted bipartite edge coloring.

Arindam Khan, PhD Thesis, Advisor: Prasad Tetali.

Thesis committee members: Nikhil Bansal (reader), Santosh Vempala, Dana Randall, Santanu Dey, Sebastian Pokutta.

Georgia Institute of Technology, Atlanta, USA, 2015.
(pdf)

Abstract: The bin packing problem is a well-studied problem in combinatorial optimization. In the classical bin
packing problem, we are given a list of real numbers in (0, 1] and the goal is to place them in a minimum
number of bins so that no bin holds numbers summing to more than 1. The problem is extremely important
in practice and finds numerous applications in scheduling, routing and resource allocation problems.
Theoretically the problem has rich connections with discrepancy theory, iterative methods, entropy
rounding and has led to the development of several algorithmic techniques. In this survey we consider
approximation and online algorithms for several classical generalizations of bin packing problem such
as geometric bin packing, vector bin packing and various other related problems. There is also a vast
literature on mathematical models and exact algorithms for bin packing. However, this survey does not
address such exact algorithms.
In two-dimensional geometric bin packing, we are given a collection of rectangular items to be
packed into a minimum number of unit size square bins. This variant has a lot of applications in cutting
stock, vehicle loading, pallet packing, memory allocation and several other logistics and robotics related
problems. In d-dimensional vector bin packing, each item is a d-dimensional vector that needs to be
packed into unit vector bins. This problem is of great significance in resource constrained scheduling and
in recent virtual machine placement in cloud computing. We also consider several other generalizations
of bin packing such as geometric knapsack, strip packing and other related problems such as vector
scheduling, vector covering etc. We survey algorithms for these problems in offline and online setting,
and also mention results for several important special cases. We briefly mention related techniques used
in the design and analysis of these algorithms. In the end we conclude with a list of open problems.

Henrik I. Christensen, Arindam Khan, Sebastian Pokutta, Prasad Tetali.

Sreenivas Gollapudi, Arindam Khan, Janardhan Kulkarni, Kunal Talwar, Sadra Yazdanbod.

Coming soon.

Arindam Khan, Prasad Tetali.

Published Conference Papers

Abstract.

Susanne Albers, Arindam Khan, Leon Ladewig.

45th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2020
(pdf)

Recipient of best paper award in MFCS 2020.

Abstract.

Arindam Khan, Madhusudhan Reddy Pittu.

International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2020
(pdf)

Abstract.

Waldo Galvez, Fabrizio Grandoni, Afrouz Jabal Ameli, Klaus Jansen, Arindam Khan, Malin Rau.

International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2020
(pdf)

Abstract.

Susanne Albers, Arindam Khan, Leon Ladewig.

International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2019
(pdf)

Also selected for presentation in Hightlights in Algorithms (HALG), 2020.

We study the two-dimensional geometric knapsack problem (2DK), a geometric variant of the classical knapsack problem. In this problem we are given a set of axis-aligned rectangular items, each one with an associated profit, and an axis-aligned square knapsack. The goal is to find a (non-overlapping) packing of a maximum profit subset of items inside the knapsack without rotating items. This is a very well-studied optimization problem and finds applications in scheduling, memory allocation, advertisement placement etc. The best-known polynomial-time approximation factor for this problem (even just in the cardinality case) is $2+\eps$ [Jansen and Zhang, SODA 2004].
After more than a decade, in this paper we break the 2-approximation barrier, achieving a polynomial-time $17/9+\eps<1.89$ approximation, which improves to $558/325+\eps<1.72$ in the cardinality case.
We also consider the variant of the problem with rotations (2DKR) , where the items can be rotated by $90$ degrees. Also in this case the best-known polynomial-time approximation factor (even for the cardinality case) is $2+\eps$ [Jansen and Zhang, SODA 2004]. Exploiting part of the machinery developed for 2DK plus a few additional ideas, we obtain a polynomial-time $3/2+\eps$-approximation for 2DKR, which improves to $4/3+\eps$ in the cardinality case.

Waldo Galvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, Andreas Wiese.

58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2017.
(pdf)

my FOCS TALK: (Slides,
Video),
A longer 64 page version: (Arxiv)

Gives improved approximation for a classical problem after thirteen years.

Also selected for presentation in Hightlights in Algorithms (HALG), 2018.

We study the strip packing problem, a classical packing problem which generalizes both bin packing and makespan minimization. Here we are given a set of axis-parallel rectangles in the two-dimensional plane and the goal is to pack them in a vertical strip of fixed width such that the height of the obtained packing is minimized. The packing must be non-overlapping and the rectangles cannot be rotated. A reduction from the partition problem shows that no approximation better than 3/2 is possible for strip packing in polynomial time (assuming P!=NP). Nadiradze and Wiese [SODA16] overcame this barrier by presenting a (7/5+epsilon)-approximation algorithm in pseudo-polynomial-time (PPT). As the problem is strongly NP-hard, it does not admit an exact PPT algorithm (though a PPT approximation scheme might exist). In this paper we make further progress on the PPT approximability of strip packing, by presenting a (4/3+epsilon)-approximation algorithm. Our result is based on a non-trivial repacking of some rectangles in the "empty space" left by the construction by Nadiradze and Wiese, and in some sense pushes their approach to its limit. Our PPT algorithm can be adapted to the case where we are allowed to rotate the rectangles by 90 degrees, achieving the same approximation factor and breaking the polynomial-time approximation barrier of 3/2 for the case with rotations as well

Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2016.
(pdf)

my FSTTCS TALK: (Slides),
A longer 20 page version:( Arxiv)

We study the $d$-dimensional vector bin packing problem, a well-studied generalization of bin packing arising in resource
allocation and scheduling problems.
Here we are given a set of $d$-dimensional vectors $v_1, \ldots, v_n$ in $[0,1]^d$,
and the goal is to pack them into the least number of bins so that for each bin $B$, the sum of the vectors in it is at most $1$ in every dimension, i.e., $||\sum_{v_i \in B} v_i ||_{\infty} \le 1$.
For the $2$-dimensional case we give an asymptotic approximation guarantee
of $1+\ln(1.5)+\epsilon \approx (1.405+\epsilon)$, improving upon the previous bound of $1+\ln 2+\epsilon \approx (1.693+\epsilon)$. We also give an almost tight $(1.5+\epsilon)$
absolute approximation guarantee,
improving upon the previous bound of 2 \cite{kellerer2003approximation}.
For the $d$-dimensional case, we get a $1.5+\ln (\frac{d}2)+ o_d(1)+\epsilon$ guarantee, improving upon the previous $(1+\ln d+\epsilon)$ guarantee \cite{BansalCS09} based on the
Round \& Approx framework.
Here $(1+ \ln d)$ was a natural barrier as rounding-based algorithms can not achieve better than $d$ approximation.
We get around this by exploiting
various structural properties of
(near)-optimal packings, and using multi-objective multi-budget matching based techniques and
expanding the R \& A framework to go beyond rounding-based algorithms.
Along the way we also prove several results that could be of independent interest.

Nikhil Bansal, Arindam Khan, Marek Elias

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016.
(pdf)

Gives improved approximation for a classical problem after a decade.

We consider weighted bipartite edge coloring problem which is a generalization of bin packing and edge coloring and is inspired from the study of Clos networks. In the problem, given a weighted
bipartite graph the goal is to color all edges with minimum number of colors such that the sum of the edges incident to any vertex of any color is at most one. Chung and Ross conjectured that there is a proper weighted coloring with 2n-1 colors where n denotes the maximum over all vertices of the number of unit sized bins needed to pack the weights of edges incident to the vertex.
We show a constructive proper weighted coloring by 20n/9 color improving previous 9/4 approximation by Feige et al.
We further show that 11n/5 colors are sufficient when all edges are >1/4.

Arindam Khan, Mohit Singh

Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2015.
(pdf)

We study the two-dimensional bin packing problem
with and without rotations. Here we are given a set of
two-dimensional rectangular items I and the goal is
to pack these into a minimum number of unit square
bins. We consider the orthogonal packing case where
the edges of the items must be aligned parallel to
the edges of the bin. Our main result is a 1.405-
approximation for two-dimensional bin packing with
and without rotation, which improves upon a recent
1.5 approximation due to Jansen and Praedel. We also
show that a wide class of rounding based algorithms
cannot improve upon the factor of 1.5.

Nikhil Bansal, Arindam Khan.

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.
(pdf)

Gives a unified framework for a class of bin packing algorithms called O(1) rounding-based algorithms.
For a more detailed version of the result in this paper, please see chapter III of my PhD thesis.

Abstract: Social networks serve as important platforms for users to express, exchange and form opinions on various topics. Several
opinion dynamics models have been proposed to characterize
how a user iteratively updates her expressed opinion based
on her innate opinion and the opinion of her neighbors. The
extent to how much a user is in
uenced by her neighboring
opinions, as opposed to her own innate opinion, is governed
by a measure of her conformity parameter. Characterizing this degree of conformity for users of a social network
is critical for several applications such as debiasing online
surveys andnding social in
uencers. In this paper, we
address the problem of estimating these conformity values
for users, using only the expressed opinions and the social
graph. We pose this problem in a constrained optimization
framework and design efficient algorithms, which we validate
on both synthetic and real-world Twitter data. Using these
estimated conformity values, we then address the problem
of identifying the smallest subset of users in a social graph
that, when seeded initially with some non-neutral opinions,
can accurately explain the current opinion values of users
in the entire social graph. We call this problem seed recovery. Using ideas from compressed sensing, we analyze and
design algorithms for both conformity estimation and seed
recovery, and validate them on real and synthetic data.

Abhimanyu Das, Sreenivas Gollapudi, Arindam Khan and Renato Paes Leme.

ACM Conference on Online Social Networks (COSN), 2014.
(pdf)

Abstract: The problem of ordering a set of entities which contain
inherent ties among them arises in many applications.
Notion of �bucket order� has emerged as a popular
mechanism of ranking in such settings. A bucket
order is an ordered partition of the set of entities into
�buckets�. There is a total order on the buckets, but
the entities within a bucket are treated as tied.
In this paper, we focus on discovering bucket order
from data captured in the form of user preferences. We
consider two settings: one in which the discrepancies in
the input preferences are �local� (when collected from
experts) and the other in which discrepancies could
be arbitrary (when collected from a large population).
We present a formal model to capture the setting of
local discrepancies and consider the following question:
�how many experts need to be queried to discover
the underlying bucket order on n entities?�. We
prove an upperbound of O(log n ^ 1/2). In the case of
arbitrary discrepancies, we model it as the bucket
order problem of discovering a bucket order that
best fits the data (captured as pairwise preference
statistics). We present a new approach which exploits
a connection between the discovery of buckets and the
correlation clustering problem. We present empirical
evaluation of our algorithms on real and artificially
generated datasets.

Sreyash Kenkre, Arindam Khan and Vinayaka Pandit.

SIAM International Conference on Data Mining (SDM), 2011.
(pdf)

Published Journal Papers

On the Matching Augmentation Problem.
The high-level goal of survivable network design is to design (cheap) networks that provide connectivity between pre-specified pairs of nodes despite a few node or edge failures. One of the most basic such problems is the Forest Augmentation Problem (FAP): we are given an undirected graph with $0$-$1$ edge costs. Our goal is to compute a min-cost subgraph which is $2$-edge connected. Intuitively, we are given some existing network (i.e., the $0$-edges), and we need to augment it (with $1$-edges) to make it resilient to one edge fault.
Note that each 2-edge connected component of $0$-edges can be contracted into a single node, hence we can assume w.l.o.g. that $0$-edges induce a forest: this motivates the name of the problem.
FAP is APX-hard [Kortsarz et al.,'04], and the best known approximation factor (that holds also for much more general problems) is $2$ [Jain,'01]. The most relevant special case of FAP where a better approximation is known is when the forest consists of a single spanning tree: the Tree Augmentation Problem (TAP) [Nagamochi,'03; Even et al.,'06; Kortsarz and Nutov,'15].
In this paper we study another relevant special case of FAP, the Matching Augmentation Problem (MAP), where $0$-edges form a matching. This captures an extremal situation where the total number of leaves is relatively small compared to the number of trees (in the opposite situation, one can easily achieve an approximation factor better than $2$ by a reduction to TAP).
For this problem we present an improved $7/4$ approximation algorithm. Our main building block is the construction of a min-cost subgraph where each node has degree at least $2$. This is later augmented to the desired solution via a sequence of non-trivial steps.

Joseph Cheriyan, Jack Dippel, Fabrizio Grandoni, Arindam Khan, Vishnu V. Narayan.

Makes first progress towards Forest Augmentation Problem when the forest contains more than one trees.
The other case, Tree Augmentation Problem (TAP) i.e., when the forest is a spanning tree, is well-studied.

Given a capacitated undirected graph G=(V,E) with a set of terminals K \subset V, a mimicking network is a smaller graph H=(V_H,E_H) which contains the set of terminals K and for every bipartition [U,K\U] of the terminals, the cost of the minimum cut separating U from K\U in G is exactly equal to the cost of the minimum cut separating U from K\U in H.
In this work, we improve both the previous known upper bound of 2^2^k and lower bound of (k+1) for mimicking networks, reducing the doubly-exponential gap between them to a single-exponential gap as follows:
Given a graph G, we exhibit a construction of mimicking network with at most k'th Hosten-Morris number of vertices (independent of the size of V).
For lower bound we show that there exist graphs with k terminals that have no mimicking network with less than 2^(k-1) number of edges.
We also show improved construction for trees, outerplanar and bounded treewidth graphs.

Arindam Khan, Prasad Raghavendra.

Information Processing Letters (IPL), Volume 114, Issue 7, July 2014, Pages 365-371.
(journal version)
(pdf)

A preliminary version in Arxiv.
(Independently and parallelly, Krauthgamer and Rika obtained similar bounds in SODA 2013 )

In this paper we study the diffuse reflection diameter and diffuse reflection radius problems for convex-quadrilateralizable polygons . In the usual model of diffuse reflection, a light ray incident at a point on the reflecting surface is reflected from that point in all possible inward directions. A ray reflected from a polygonal edge may graze that reflecting edge but an incident ray cannot graze the reflecting edge. The diffuse reflection diameter of a simple polygon P is the minimum number of diffuse reflections that may be needed in the worst case to illuminate any target point t from any point light source s inside P. We show that the diameter is upper bounded by (3n-10)/4 source in our usual model of diffuse reflection for convex-quadrilateralizable polygons . To the best of our knowledge, this is the first upper bound on diffuse reflection diameter within a fraction of n for such a class of polygons. We also show that the diffuse reflection radius of a convex-quadrilateralizable simple polygon with n vertices is at most (3n-10)/8 source under the usual model of diffuse reflection. In other words, there exists a point inside such a polygon from which (3n-10)/8 usual diffuse reflections are always sufficient to illuminate the entire polygon. In order to establish these bounds for the usual model, we first show that the diameter and radius are (n-4)/2 and View (n-4)/4 respectively, for the same class of polygons for a relaxed model of diffuse reflections; in the relaxed model an incident ray is permitted to graze a reflecting edge before turning and reflecting off the same edge at any interior point on that edge. We also show that the worst-case diameter and radius lower bounds of (n-4)/2 and (n-4)/4 respectively, are sometimes attained in the usual model, as well as in the relaxed model of diffuse reflection.

Arindam Khan, Sudebkumar P. Pal, Mridul Aanjaneya, Arijit Bishnu, Subhas C. Nandy.

Attribute Based Messaging (ABM) enables messages to be addressed using attributes of recipients
rather than an explicit list of recipients. Such messaging offers benefits of efficiency, exclusiveness,
and intensionality, but faces challenges in access control and confidentiality. In this paper we
explore an approach to intra-enterprise ABM based on providing access control and confidentiality
using information from the same attribute database exploited by the addressing scheme. We show
how to address three key challenges. First, we demonstrate a manageable access control system
based on attributes. Second, we demonstrate use of Attribute Based Encryption to provide endto-
end confidentiality. Third, we show that such a system can be efficient enough to support ABM
for mid-size enterprises. Our implementation can dispatch confidential ABM messages approved
by XACML policy review for an enterprise of at least 60,000 users with only seconds of latency.

Rakesh Bobba, Omid Fatemieh, Fariba Khan, Arindam Khan, Carl A. Gunter, Himanshu Khurana and Manoj Prabhakaran.

ACM Transactions on Information and System Security (TISSEC), Volume 13 Issue 4, December 2010.
(pdf)

Other Papers

Abstract: In this paper we tried to characterize malware distribution sites by web-graph properties.

DongWon Seo, Arindam Khan and Heejo Lee.

Korean Information Processing Society (KIPS) 30th Fall Conference, Volume 15, No. 2, pages 1425-1428, Nov. 14. 2008.

Abstract: In this thesis, we consider angular visibility and diffuse reflection and study art-gallery
and fortress problems. ....

Arindam Khan, Master's Thesis, Advisor: Sudebkumar Pal.

Dept. of CSE, IIT Kharagpur, India, 2009.

Nominated for innovative Students project Award at Indian National Academy of Engineering (INAE), 2009.

Abstract: Coverage is an important issue in Wireless Sensors Networks (WSNs). It gives a measure
of the quality of surveillance, a WSN provides over a field it is designed to monitor.
Different measures of coverage capture different aspects of surveillance. In this thesis, we
studied some Geometric Characterisation and Algorithms on Coverage issues in Wireless
Sensor Networks.
�Being with and against the Thief� � The name itself says that we are working on
Coverage from both the perspective of an intruder as well as a defender. First two sections
deal with Intrusion Algorithms and last two deals with Defending algorithms, arguments
and characterisations.
In Chapter 3, we present algorithms to find the right-angled one turn longest path among
circular sensors between two points, from one point and for the general case.
In Chapter 4, we present algorithms to find the longest path among polygonal obstacles
between two points, from one point and for the general case.
Chapter 5 deals with packing arguments for strip sensors.
Chapter 6 consists of few bounds on angular visibility.

Arindam Khan, Bachelor's Thesis, Advisor: Arijit Bishnu.

Dept. of CSE, IIT Kharagpur, India, 2008.

Nominated for Best B.Tech project award, IIT Kharagpur, 2008.