Karthik Abinav Sankararaman*

I'm a PhD student in the Department of Computer Science at University of Maryland, College Park (I also received an M.S. degree from the same department). I am advised by Aravind Srinivasan. I am also fortunate to closely work with these awesome researchers.

My research interests broadly span the intersection of Algorithms, Machine Learning and Operations Research. I am interested in both theory and practice with problems broadly falling in these domains. I'm particularly inclined towards problems of algorithm design and analysis drawing tools from variety of areas including probability, statistics, linear algebra, mathematical programming, (discrete/continuous) optimization. I am especially interested in research that spans the full spectrum of theory to practice (i.e., theory informing practice and applications informing theory).
My current focus is on studying algorithmic applications in Computational Economics and Machine Learning. Representative recent problems include Online Matching, Multi-armed Bandits, Causality.

I am always open to working on projects tied to other application areas which require principled algorithmic approaches. Feel free to contact me!

Previously, I obtained a B.Tech (Hons), with a major in Computer Science and a minor in Operations Research, from Indian Institute of Technology, Madras. My brother and I spent our childhood days in the beautiful city of Bangalore, India.

*I usually go by either Karthik or Abinav. If you want to use my last name, please see the syllables for help.
(Syllables: Kar/thik A/bi/nav San/kar/a/ra/man)

My name in languages I speak, in decreasing order of proficiency!
Language Karthik Abinav Sankararaman
Tamil கார்த்திக் அபினவ் சங்கரராமன்
Kannada ಕಾರ್ತಿಕ್ ಅಭಿನವ್ ಶಂಕರಾರಾಮನ್
Hindi कार्तिक अबिनव शंकररमन

Selected Publications

(See below for more details)

  • Combinatorial Semi-Bandits with Knapsacks (AIStats 2018)
  • Allocation Problems in Ride-sharing Platforms (AAAI 2018)
  • Algorithms to Approximate Column-Sparse Packing Programs (SODA 2018)
  • Online Stochastic Matching: New Algorithms and Bounds (ESA 2016)


  • Publications

    (In all papers, the authors chose the convention of alphabetical order by last names)

  • "Assigning Tasks to Workers based on Historical Data: Online Matching with Two-sided Arrivals"
    Joint Work with John Dickerson, Aravind Srinivasan, Pan Xu
    The 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2018

    Paper Code+Dataset

    Abstract: Efficient allocation of tasks to workers is a central problem in crowdsourcing. In a typical setting, different workers arrive at different times. Similarly, different tasks arrive at different times. The goal is to assign the available workers to tasks, such that we are able to complete as many tasks as possible. Usually, the tasks are heterogeneous and have different rewards. Hence, we would like to maximize the total reward (as opposed to just the number of completed tasks). Often, the arrival times of worker "types" and task "types" are not erratic and can be predicted from historical data. In this paper, we model the problem to account for this history and propose a new mathematical model, called Online Matching with Two-Sided Arrival (OM-TSA). We have a known bipartite graph G = (U,V,E) where U is the set of worker types and V is the set of task types. An edge e = (u, v) exists iff worker u is compatible with task v. The setting proceeds in rounds for T time-steps. At each time-step, a worker u from U and a task v from V are sampled independently from two respective (known) distributions. Further, we assume the sampling processes are independent and identical across the T rounds. We assume that (1) when a worker u arrives, they stay in the sys- tem until matched and (2) when a task v arrives, it needs to be assigned to an available worker u immediately (and obtaining a reward w(u, v)); if not, we do not get any reward for this task (and the action is irrevocable). Our goal is to maximize the expected reward. Our model is a significant generalization of the classical online matching model, where one of the sets U and V , say U, is assumed to be available offline. We relax this assumption to capture the transient nature of worker arrivals. For the general version of OM-TSA, we present an optimal non-adaptive algorithm which achieves an online competitive ratio of 0.295. For the special case of OM-TSA where the reward is a function of just the worker type, we present an improved algorithm (which is adaptive) and achieves a competitive ratio of at least 0.345. On the hardness side, along with showing that the ratio obtained by our non-adaptive algorithm is the best possible among all non-adaptive algorithms, we further show that no (adaptive) algorithm can achieve a ratio better than 0.581 (unconditionally), even for the special case of OM-TSA with homogenous tasks (i.e., all rewards are same). At the heart of our analysis lies a new technical tool (which is a refined notion of the birth-death process) called the two-stage birth-death process, which may be of independent interest. Finally, we perform numerical experiments on both simulated as well as two real-world datasets obtained from crowdsourcing platforms to complement our theoretical results.

    Keywords: Randomized Algorithms; Online Algorithms; Artificial Intelligence; Applications



  • "Combinatorial Semi-Bandits with Knapsacks"
    Joint Work with Aleksandrs Slivkins
    The 21st International Conference on Artificial Intelligence and Statistics (AIStats), 2018
    (Invited for Oral Presentation)
    (Top 5% of submissions)

    Paper Simulations

    Abstract: This paper unifies two lines of work on multi-armed bandits, Bandits with Knapsacks (BwK) and semi-bandits. The former concerns scenarios with limited "resources" consumed by the algorithm, e.g., limited inventory in a dynamic pricing problem. The latter has a huge number of actions, but there is combinatorial structure and additional feedback which makes the problem tractable. Both lines of work has received considerable recent attention, and are supported by numerous application examples. We define a common generalization, and design a general algorithm for this model. Our regret rates are comparable with those for BwK and semi-bandits in general, and essentially optimal for important special cases.

    Keywords: Randomized Algorithms; Online Learning; Theory of Computation; Machine Learning



  • "Allocation Problems in Ride-Sharing Platforms: Online Matching with Offline Reusable Resources"
    Joint Work with John Dickerson, Aravind Srinivasan, Pan Xu
    The 32nd AAAI Conference on Artificial Intelligence (AAAI), 2018
    (Oral Presentation)

    Paper

    Abstract: Bipartite matching markets pair agents on one side of a market with agents, items, or contracts on the opposing side. Prior work addresses online bipartite matching markets, where agents arrive over time and are dynamically matched to a known set of disposable resources. In this paper, we propose a new model, Online Matching with (offline) Reusable Resources under Known Adversarial Distributions (OM-RR-KAD), in which resources on the offline side are reusable instead of disposable; that is, once matched, resources become available again at some point in the future. We show that our model is tractable by presenting an LP-based adaptive algorithm that achieves an online competitive ratio of 1/2 − ε for any given ε > 0. We also show that no non-adaptive algorithm can achieve a ratio of 1/2 + o(1) based on the same benchmark LP. Through a data-driven analysis on a massive openly-available dataset, we show our model is robust enough to capture the application of taxi dispatching service. We also present heuristics that perform well in practice.

    Keywords: Randomized Algorithms; Online Algorithms; Artificial Intelligence; Applications



  • "Algorithms to Approximate Column-Sparse Packing Programs"
    Joint Work with Brian Brubach, Aravind Srinivasan, Pan Xu
    The 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018

    Paper

    Abstract: Column-sparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas, (non-uniform) attenuation and multiple-chance algorithms, to obtain improved approximation algorithms for some well-known families of such problems. As three main examples, we attain the integrality gap, up to lower-order terms, for known LP relaxations for k-column sparse packing integer programs (Bansal et al., Theory of Computing, 2012) and stochastic k-set packing (Bansal et al., Algorithmica, 2012), and go “half the remaining distance” to optimal for a major integrality-gap conjecture of Furedi, Kahn and Seymour on hypergraph matching (Combinatorica, 1993).

    Keywords: Randomized Algorithms; Theory of Computation



  • "Attenuate Locally, Win Globally: Attenuation-based Frameworks for Online Stochastic Matching with Timeouts"
    Joint Work with Brian Brubach, Aravind Srinivasan, Pan Xu
    The 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2017

    Paper

    Abstract: The Online Stochastic Matching with Timeouts problem introduced by Bansal, Gupta, Li, Mestre, Nagarajan, and Rudra (Algorithmica, 2012) models matching markets (e.g. E-Bay, Amazon). Buyers arrive from an independent and identically distributed (i.i.d.) known distribution on buyer profiles and can be shown a list of items one at a time. Each buyer has some probability of purchasing each item and a limit (timeout) on the number of items they can be shown. Bansal et al. (Algorithmica, 2012) gave a 0.12-competitive algorithm which was improved by Adamczyk, Grandoni, and Mukherjee (ESA, 2015) to 0.24. We present an online attenuation framework that uses an algorithm for offline stochastic matching as a black box. Our main contributions are as follows. On the upper bound side, we show that this framework combined with a black box adapted from Bansal et al. (Algorithmica, 2012) yields an online algorithm which nearly doubles the ratio to 0.46. On the lower bound side, we show that no algorithm can achieve a ratio better than 0.632 using the common LP for this problem. We then introduce a natural generalization: Online Stochastic Matching with Two-sided Timeouts in which both online and offline vertices have timeouts. Our framework provides the first algorithm for this problem achieving a ratio of 0.31. We accomplish this by proposing a new black box algorithm for offline stochastic matching on star graphs, which may be of independent interest. This new black box improves the approximation ratio for the offline stochastic matching problem on star graphs from 0.5 by Adamczyk et al. (ESA 2015) to 0.56.

    Keywords: Randomized Algorithms; Online Algorithms; Theory of Computation



  • "New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching"
    Joint Work with Brian Brubach, Aravind Srinivasan, Pan Xu
    The 24th Annual European Symposium on Algorithms (ESA), 2016

    Paper

    Abstract: We develop algorithms with improved competitive ratios for some basic variants of the known i.i.d. arrival model with integral arrival rates, including (a) the case of general weighted edges, where we improve the best-known ratio of 0.667 due to Haeupler, Mirrokni and Zadimoghaddam to 0.705 and (b) the vertex-weighted case, where we improve the 0.7250 ratio of Jaillet and Lu to 0.7299. We also consider two extensions, one is known I.I.D. with non-integral arrival rate and stochastic rewards. The other is known I.I.D. b-matching with non-integral arrival rate and stochastic rewards. We present a simple non-adaptive algorithm which works well simultaneously on the two extensions.

    Keywords: Randomized Algorithms; Online Algorithms; Theory of Computation



  • "Ensuring Privacy in Location Based Services: An Approach Based on Opacity Enforcement"
    Joint work with Yi-Chin Wu, St`ephane Lafortune.
    The 14th International Workshop of Discrete Event Systems (WODES), 2014

    Paper

    Abstract: With the proliferation of mobile devices, Location-Based Services (LBS) that provide networked services based on users’ locations have become increasingly popular. Such services, providing personalized and timely information, have raised privacy concerns such as unwanted revelation of users’ current locations to potential stalkers. In this work, we show that this problem can be formally (for first time) addressed using the notion of opacity in discrete event systems. We use non-deterministic finite-state automata to capture the mobility patterns of users and label the transitions by the location information in the queries. Using opacity verification techniques, we show that the technique of sending cloaking queries to the server can still reveal the exact location of the user. To enforce location privacy, we apply the opacity enforcement technique by event insertion. Specifically, we synthesize suitable insertion functions that insert fake queries into the cloaking query sequences. The generated fake queries are always consistent with the mobility model of the user and provably ensure privacy of the user’s current location. Finally, to minimize the overhead from fake queries, we design an optimal insertion function that introduces minimum average number of fake queries.

    Keywords: Discrete Event Systems; Formal Verification; Applications





  • Technical Reports

  • "Semi-Bandit Feedback: A survey of results (2015)"
    PDF
  • "Maximum-Flow problem in undirected graphs"
    Karthik Abinav S
    B.Tech Thesis, 2014, Indian Institute Technology Madras
    (Thesis available on request)
  • Teaching Experience

    I have served as a Teaching Assistant for the following classes during my time at UMD
  • Graduate Algorithms (Spring 2018)
    Instructors: Aravind Srinivasan

  • Design and Analysis of Computer Algorithms (Fall 2016, Spring 2017, Fall 2017)
    Instructors: Samir Khuller, Jessica Chang, Aravind Srinivasan

  • Discrete Structures (Fall 2014 and Spring 2015)
    Instructors: Clyde Kruskal, Fawzi Emad

  • Introduction to Programming (Fall 2015 and Spring 2016)
    Instructors: Nelson Padua-Perez, Fawzi Emad

  • As an undergrad I have served as a Teaching Assistant at IITM.
  • Paradigms of Programming(IITM)
    Instructors: Narayanaswamy NS
  • Industry/Other Research Experience

    Microsoft Research, New York City

    I am spending the Summer 2018 (June-Septmber) at Microsoft Research, New York City working with Nicole Immorlica, Rob Schapire and Alex Slivkins.

    Indian Institute of Science and Microsoft Research, Bangalore

    I spent the Summer of 2017 at IISc and Microsoft Research, Bangalore working with Anand Louis and Navin Goyal. We studied problems in Causal Inference.

    IBM Almaden Research Center, San Jose

    I spent the Summer of 2016 at IBM Almaden Research center, working with Prithviraj Sen. We worked on problems in applied machine learning.

    Adobe Inc.

    I spent the Summer of 2015 at Adobe Systems Inc, at their San Jose office. I worked with the Algorithms team inside the Digital Marketing team headed by Anil Kamath. I was involved in an applied algorithms project in databases. I was working on Online Entity Resolution problem.

    Miscellanous Writings - Academic and Non-Academic

  • Blog hosted here Blog.

  • A critique I wrote for the Computational Journalism class.
    The article is a critque on FiveThirtyEight publication Best and Worst Airlines.
    Critique

  • Final project for the Computational Journalism class on Bias in Google's Autocomplete Suggestion.
    Along with Daniel Trielli, we studied the bias in auto-complete suggestions of various country specific
    domains of Google when searched about entities of other countries.
    (For example, searching about Pakistan in India-specific Google page).
    You can find the code used for the experiments here.
    Article summarizing the methodologies and findings

  • Final class project for the Convex Optimization class.
    Along with Manasij Venkatesh and Aditya Acharya, we looked at sparse representations for speech
    using Convex Optimization based approximations. In particular, we applied techniques from compressed
    sensing literature to speech.
    Report, Poster, code

  • Final class project for the Lower Bounds in Algorithms class.
    Along with Tommy Pensyl and Bartosz Rybicki (visiting from Poland), we studied
    lower bounds for fault tolerant variations of the facility location problem.
    Report

  • Feel free to contact me

    The best way to contact me is through email.

    Email

    kabinav@cs.umd.edu

    Phone

    +1 240 715 5910

    Address

    3204, A.V. Williams Building,
    University of Maryland,
    College Park, MD, 20742