Research

Research Interests

• Approximation Algorithms, Graph Algorithms and Combinatorial Optimization,
• Online Algorithms and Online Learning,
• Computational Geometry and Parameterized Algorithms

Publications ( DBLP , Google Scholar )

(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.

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.

Computer Science Review 24: 63-79, 2017. (journal version), (pdf),

Contains TEN interesting open problems.

Manuscripts/Submissions

• Coming soon.

Klaus Jansen, Arindam Khan, Malin Rau.

• Coming soon.

Deval Patel, Arindam Khan, Anand Louis.

• Coming soon.

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

• Coming soon.

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.

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

Waldo Galvez, Fabrizio Grandoni, Salvatore Ingala, Arindam Khan.

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.

my SODA TALK: (Slides)

• 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)

my FSTTCS TALK: (Slides)

• 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)

my SODA TALK: (Slides)

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 and nding 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.

Mathematical Programming , vol 182, pages 315–354, 2020. (Arxiv version).

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.

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.

Discrete Applied Mathematics, Volume 161, Issues 10-11, July 2013, Pages 1496-1505. (journal version) (pdf)

• 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.