# Deeparnab Chakrabarty

According to our database

Collaborative distances:

^{1}, Deeparnab Chakrabarty authored at least 65 papers between 2005 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2019

Approximation algorithms for minimum norm and ordered optimization problems.

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Adaptive Boolean Monotonicity Testing in Total Influence Time.

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018

Online Buy-at-Bulk Network Design.

SIAM J. Comput., 2018

Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions on Hypergrids.

Electronic Colloquium on Computational Complexity (ECCC), 2018

Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling.

Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Dynamic Algorithms for Graph Coloring.

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median.

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Generalized Center Problems with Outliers.

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

A o(d) · polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]

^{d}.
Electronic Colloquium on Computational Complexity (ECCC), 2017

A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube.

Electronic Colloquium on Computational Complexity (ECCC), 2017

Subquadratic submodular function minimization.

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

The Heterogeneous Capacitated k-Center Problem.

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time.

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps.

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Monotonicity Testing.

Encyclopedia of Algorithms, 2016

Max-Min Allocation.

Encyclopedia of Algorithms, 2016

Special Issue: APPROX-RANDOM 2014: Guest Editors' Foreword.

Theory of Computing, 2016

An o(n) Monotonicity Tester for Boolean Functions over the Hypercube.

SIAM J. Comput., 2016

Facility Location with Client Latencies: LP-Based Techniques for Minimum-Latency Problems.

Math. Oper. Res., 2016

Detecting Character Dependencies in Stochastic Models of Evolution.

Journal of Computational Biology, 2016

A Õ(n) Non-Adaptive Tester for Unateness.

Electronic Colloquium on Computational Complexity (ECCC), 2016

IQ-Hopping: distributed oblivious channel selection for wireless networks.

Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2016

The Non-Uniform k-Center Problem.

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Recognizing Coverage Functions.

SIAM J. Discrete Math., 2015

On (1,

*∊*)-Restricted Assignment Makespan Minimization.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties.

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Online Buy-at-Bulk Network Design.

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Submodularity Helps in Nash and Nonsymmetric Bargaining Games.

SIAM J. Discrete Math., 2014

Provable Submodular Minimization using Wolfe's Algorithm.

Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Welfare maximization and truthfulness in mechanism design with ordinal preferences.

Proceedings of the Innovations in Theoretical Computer Science, 2014

2013

Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids.

Proceedings of the Symposium on Theory of Computing Conference, 2013

A o(n) monotonicity tester for boolean functions over the hypercube.

Proceedings of the Symposium on Theory of Computing Conference, 2013

Budget smoothing for internet ad auctions: a game theoretic approach.

Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

An Optimal Lower Bound for Monotonicity Testing over Hypergrids.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

Capacitated Network Design on Undirected Graphs.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Review of design of approximation algorithms, by David P. Williamson and David B. Shmoys.

SIGACT News, 2012

Optimal bounds for monotonicity and Lipschitz testing over the hypercube.

Electronic Colloquium on Computational Complexity (ECCC), 2012

Approximability of the Firefighter Problem - Computing Cuts over Time.

Algorithmica, 2012

Testing Coverage Functions.

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Approximability of Sparse Integer Programs.

Algorithmica, 2011

Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems.

Proceedings of the Integer Programming and Combinatoral Optimization, 2011

Approximability of Capacitated Network Design.

Proceedings of the Integer Programming and Combinatoral Optimization, 2011

Social Welfare in One-Sided Matching Markets without Money.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Rationality and Strongly Polynomial Solvability of Eisenberg--Gale Markets with Two Agents.

SIAM J. Discrete Math., 2010

Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound.

Oper. Res. Lett., 2010

G-parking functions, acyclic orientations and spanning trees.

Discrete Mathematics, 2010

Hypergraphic LP Relaxations for Steiner Trees.

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

On Column-Restricted and Priority Covering Integer Programs.

Proceedings of the Integer Programming and Combinatorial Optimization, 2010

2009

Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity.

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Algorithms for Message Ferrying on Mobile ad hoc Networks.

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

On Allocating Goods to Maximize Fairness.

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

Algorithmic aspects of connectivity, allocation and design problems.

PhD thesis, 2008

Budget constrained bidding in keyword auctions and online knapsack problems.

Proceedings of the 17th International Conference on World Wide Web, 2008

Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems.

Proceedings of the Internet and Network Economics, 4th International Workshop, 2008

Efficiency, Fairness and Competitiveness in Nash Bargaining Games.

Proceedings of the Internet and Network Economics, 4th International Workshop, 2008

New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem.

Proceedings of the Integer Programming and Combinatorial Optimization, 2008

On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP.

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Public Advertisement Broker Markets.

Proceedings of the Internet and Network Economics, Third International Workshop, 2007

On Competitiveness in Uniform Utility Allocation Markets.

Proceedings of the Internet and Network Economics, Third International Workshop, 2007

2006

Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity.

Electronic Colloquium on Computational Complexity (ECCC), 2006

New Results on Rationality and Strongly Polynomial Time Solvability in Eisenberg-Gale Markets.

Proceedings of the Internet and Network Economics, Second International Workshop, 2006

Design Is as Easy as Optimization.

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

Fairness and optimality in congestion games.

Proceedings of the Proceedings 6th ACM Conference on Electronic Commerce (EC-2005), 2005