Dr. Arindam Khan   Now I am an Assistant Professor in the Department of Computer Science and Automation at Indian Institute of Science, Bengaluru, India. This webpage will longer be maintained. Please email me at my present email address: arindamkhan@iisc.ac.in (Past) Researcher Chair of Algorithms and Complexity Institute for Informatics TU Munich, Germany PhD, ACO (Computer Science), Georgia Tech, 2010-2015. Advisor: Prof. Prasad Tetali MS, Mathematics, Georgia Tech, 2010-2015. B.Tech+M.Tech, Computer Science & Engineering, Indian Institute of Technology (IIT) Kharagpur, 2004-2009.

About me:

I am a Researcher in the Chair of Algorithms and Complexity at Technical University of Munich, Germany.

• Algorithms and Complexity Group, IDSIA, Lugano, Switzerland; (Ricercatore (Researcher), 2015-17)
• Theory Group, MSR Redmond; (Mentor: Mohit Singh, Summer Intern, 2014)
• Simons Institute, UC Berkeley; (Host: Prasad Raghavendra, Fall, 2013)
• Microsoft Research Silicon Valley; (Summer Intern: Summer 2013)
• TU Eindhoven; (Host: Nikhil Bansal, Spring 2013 and Fall 2014).
• Analytics and Optimization group, IBM Research. (Blue Scholar , 2009-10).
• Security Lab, University of Illinois, Urbana-Champaign. (UG Summer Intern, Summer 2007).

In the past I have organized a Reading Group on Algorithmic Techniques in Georgia Tech and presently started the same in TU Munich.

Top

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

Top

pdf

Top

 

Manuscripts/Submissions



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
Submitted to journal: Mathematical Programming (Pdf).
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.


On Minimum Linear Ordering Problems. Iwata et. al. introduced Minimum Linear Ordering Problem, which generalizes several combinatorial problems such as the Minimum Linear Arrangement(MLA), Min Sum Set Cover(MSSC), Min Sum Vertex Cover(MSVC) problems. In this paper we study Minimum Linear Ordering Problem(MLOP) under submodular functions. We also introduce Min-max Linear Ordering(MMLO) problem which generalizes combinatorial problems such as the Min Cut Linear Arrangement(MCLA). We give approximation algorithms for submodular MMLO, submodular MLOP and symmetric submodular MLOP.

Arindam Khan, Prasad Tetali



On Polynomial-time Absolute Approximation for Strip Packing.

Waldo Galvez, Fabrizio Grandoni, Klaus Jansen, Arindam Khan and Malin Rau.



On Randomized Greedy Matching Game.

Susanne Albers and Arindam Khan.



Online Algorithms for Knapsack under Random-order Arrival.

Susanne Albers, Arindam Khan and Leon Ladewig.



Scheduling Algorithms for Smart-Grid Allocation.

Klaus Jansen, Arindam Khan and Malin Rau.



A Geometric Approach to Diverse Group Formation. Group formation is one of the central phenomenon underlying the dynamics of social interactions. Specifically, in the context of personal achievement and shared goals, groups have been shown to improve the performance of individuals participating in the group. This admits different notions of group utility often derived from user preferences or attributes. Further, any notion of group utility has a bearing on the individual utility a user derives by joining the group. In particular, this makes the joining of a group by a user an individual decision giving the user freedom to choose the right group and move away from the group if the derived utility from the group decreases. We study the dynamics resulting from such user behavior in group formation in the settings where it is desirable to bring users with diverse skill sets to work as a team. By mapping user attributes or skills as points in a higher dimensional space, we define natural notions of group utilities and user utilities based on the participating agents in the group. This induces a {\em game} among agents who team up to form groups so as to maximize their own utilities. We characterize the {\em strong Nash equilibria} resulting from the coalitional strategies of the users. We show that the {\em strong price of anarchy} (strong PoA) of the resulting equilibrium is at most $4$ for bounded size group formation games where the size of every group is at most $g$. In another natural setting when the size of every group is constrained to be equal to $g$, we show that the strong PoA is at most $6$. We also show a lower bound of $2$ on the strong PoA in both the settings. Finally, we prove that the optimization version of the problem is NP-hard and provide constant approximation algorithm for the same.

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



 

Publications


⊞ indicates that the paper was presented in the conference by me.
⊞ Approximating Geometric Knapsack via L-packings 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): 260-271, 2017.
Gives improved approximation for a classical problem after thirteen years.
my FOCS TALK:( Slides, Video )
A longer 64 page version:( Arxiv)



Approximation and online algorithms for multidimensional bin packing: A survey.

Henrik I. Christensen, Arindam Khan, Sebastian Pokutta, Prasad Tetali
Computer Science Review 24: 63-79 (2017) .
SURVEY PAPER: contains interesting TEN open problems.


⊞ Improved Pseudo-Polynomial-Time Approximation for Strip Packing. 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.
my FSTTCS TALK:( Slides)
A longer 20 page version:( Arxiv)


⊞ Improved Approximation For Vector Packing. 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, Marek Elias, Arindam Khan
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016.
Gives improved approximation for a classical problem after a decade.
my SODA TALK:( Slides)



⊞ On Weighted Bipartite Edge Coloring. 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.
my FSTTCS TALK:( Slides)



Approximation Algorithm for Multidimensional Bin Packing.

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.



⊞ An Improved Approximation Algorithm for Two-Dimensional Bin Packing. 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.
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.


On Mimicking Networks Representing Minimum Terminal Cuts. 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.
A preliminary version in Arxiv.
(Independently and parallelly, Krauthgamer and Rika obtained similar bounds in SODA 2013 )


Role of Conformity in Opinion Dynamics in Social Networks. 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.


Diffuse Reflection Diameter and Radius for Convex Quadrilateralizable Polygons. 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.


Discovering Bucket Orders from Data. 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.


Attribute-based messaging: Access control and confidentiality. 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 .


A Study on Detecting Malcodes Distribution Sites. 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.


Polygon and Fortress Guarding by Diffuse Reflection, Angular Visibility and Direct Visibility. In this thesis, we consider angular visibility and diffuse reflection and study art-gallery and fortress problems.

under Prof. Sudebkumar P. Pal, Dept. of CSE, IIT Kharagpur, India
Masters Thesis, 2009.
Nominated for innovative Students project Award at Indian National Academy of Engineering (INAE), 2009.


Being with and against the Thief:
Geometric Characterization and Algorithms on Coverage Issues in Wireless Sensor Networks. 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.

under Prof. Arijit Bishnu, Dept. of CSE, IIT Kharagpur, India
Bachelors Thesis, 2008.
Nominated for Best B.Tech project award, IIT Kharagpur, 2008.

Top

At ISI Kolkata:
• Approximation Algorithms: Research Course(Fall 2015)(Co-taught with Arijit Bishnu)
At Georgia Tech:
• CS4510: Automata and Complexity(Spring 2012)(Nominated for CETL/BP Outstanding GTA)
• CS6505: Computability and Algorithms(Spring 2013)
• CS4540: Advanced Algorithms(Spring 2014) (taught Linear Programs and Approximation Algorithms)
• CS4510: Automata and Complexity(Spring 2014)(held monthly review sessions)
• CS6505: Computability, Complexity and Algorithms(Spring 2014)(Taught Approximation Algorithms) Some of my lecture Notes: SetCover, TSP, maxCut
• CS3510: Design and Analysis of Algorithms(Spring 2015)
At IIT Kharagpur:
• Algorithms -II (Fall 2008)
• Computer Architecture and Operating Systems (Spring 2009)
• Computational Geometry (Spring 2009)

Top

• (Short) LaTex Symbols
• The Comprehensive LATEX Symbol List
• Upcoming CS Theory Conference Deadlines
• Upcoming CS Theory Conferences
• Acceptance Rate/Statistics on CS Theory Conferences
• Discrete Math/Combinatorics Journals rankings
• TCS Blog Aggregator
• New in Arxiv
• OTHER INTERESTING LINKS

Top