Arindam Khan Homepage

Arindam Khan

PhD (completed) in ACO.
College of Computing
Georgia Institute of Technology, Atlanta, USA
email: akhan67 [at] gatech dot edu

About Me | Research Interests | Resume(CV) | Papers | Courses done | Links | Site Statistics

I completed my PhD in Algorithms, Combinatorics and Optimization program at the College of Computing. I was advised by Prasad Tetali. I will soon join IDSIA, Lugano.

IBM Research, India

I have organized a Reading Group on Algorithmic Techniques in the past.

Research Interests:

Approximation Algorithms and Combinatorial Optimization
Algorithmic Game Theory
Computational Geometry and Graph Algorithms

Resume(CV):

Papers and Technical Reports:

Thesis

Approximation Algorithms for Multidimensional Bin Packing. Thesis

Georgia Institute of Technology, Atlanta, USA. August, 2015.

Manuscripts/Submissions

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

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.

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.

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

Publications

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.
TALK:( Slides)

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.

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.

Courses done

Coursera

Quantum Computing(Sum12- Umesh Vazirani)

Teaching

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

Links

(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
ACO Student Seminar at GaTech
Leveraging MOOC(Massive Open Online Course)
OTHER INTERESTING LINKS

hit counter for tumblr

^th

^th