default search action
Deeparnab Chakrabarty
Person information
- affiliation: Dartmouth College, Hanover, NH, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [c62]Hang Liao, Deeparnab Chakrabarty:
Learning Spanning Forests Optimally in Weighted Undirected Graphs with CUT queries. ALT 2024: 785-807 - [c61]Deeparnab Chakrabarty, Hang Liao:
Learning Partitions Using Rank Queries. FSTTCS 2024: 16:1-16:14 - [c60]Deeparnab Chakrabarty, Luc Côté, Ankita Sarkar:
Fault-tolerant k-Supplier with Outliers. STACS 2024: 23:1-23:19 - [i67]Deeparnab Chakrabarty, C. Seshadhri:
Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing. CoRR abs/2409.02206 (2024) - [i66]Deeparnab Chakrabarty, Hang Liao:
Learning Partitions using Rank Queries. CoRR abs/2409.13092 (2024) - 2023
- [j27]Deeparnab Chakrabarty, Maryam Negahbani:
Robust k-center with two types of radii. Math. Program. 197(2): 991-1007 (2023) - [c59]Deeparnab Chakrabarty, Hang Liao:
A Query Algorithm for Learning a Spanning Forest in Weighted Undirected Graphs. ALT 2023: 259-274 - [c58]Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
A d1/2+o(1) Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids. FOCS 2023: 1796-1821 - [c57]Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford:
Parallel Submodular Function Minimization. NeurIPS 2023 - [c56]Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester. STOC 2023: 233-241 - [i65]Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
A d1/2+o(1) Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids. CoRR abs/2304.01416 (2023) - [i64]Hang Liao, Deeparnab Chakrabarty:
Learning Spanning Forests Optimally using CUT Queries in Weighted Undirected Graphs. CoRR abs/2306.10182 (2023) - [i63]Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford:
Parallel Submodular Function Minimization. CoRR abs/2309.04643 (2023) - [i62]Deeparnab Chakrabarty, Luc Côté, Ankita Sarkar:
Fault-tolerant k-Supplier with Outliers. CoRR abs/2310.07208 (2023) - [i61]Deeparnab Chakrabarty, Luc Côté:
A Primal-Dual Analysis of Monotone Submodular Maximization. CoRR abs/2311.07808 (2023) - [i60]Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
A d1/2+o(1) Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [c55]Deeparnab Chakrabarty, Maryam Negahbani, Ankita Sarkar
:
Approximation Algorithms for Continuous Clustering and Facility Location Problems. ESA 2022: 33:1-33:15 - [c54]Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford:
Improved Lower Bounds for Submodular Function Minimization. FOCS 2022: 245-254 - [i59]Deeparnab Chakrabarty, Maryam Negahbani, Ankita Sarkar:
Approximation Algorithms for Continuous Clustering and Facility Location Problems. CoRR abs/2206.15105 (2022) - [i58]Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford:
Improved Lower Bounds for Submodular Function Minimization. CoRR abs/2207.04342 (2022) - [i57]Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester. CoRR abs/2211.05281 (2022) - [i56]Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $\widetilde{O}(n\sqrt{d})$ Monotonicity Tester. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j26]Deeparnab Chakrabarty, Sanjeev Khanna:
Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling. Math. Program. 188(1): 395-407 (2021) - [c53]Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna:
Graph Connectivity and Single Element Recovery via Linear and OR Queries. ESA 2021: 7:1-7:19 - [c52]Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna:
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization. FOCS 2021: 37-48 - [c51]Tanvi Bajpai, Deeparnab Chakrabarty, Chandra Chekuri, Maryam Negahbani:
Revisiting Priority k-Center: Fairness and Outliers. ICALP 2021: 21:1-21:20 - [c50]Deeparnab Chakrabarty, Maryam Negahbani:
Robust k-Center with Two Types of Radii. IPCO 2021: 268-282 - [c49]Maryam Negahbani, Deeparnab Chakrabarty:
Better Algorithms for Individually Fair k-Clustering. NeurIPS 2021: 13340-13351 - [i55]Deeparnab Chakrabarty, Maryam Negahbani:
Robust $k$-Center with Two Types of Radii. CoRR abs/2102.11435 (2021) - [i54]Tanvi Bajpai, Deeparnab Chakrabarty, Chandra Chekuri, Maryam Negahbani:
Revisiting Priority k-Center: Fairness and Outliers. CoRR abs/2103.03337 (2021) - [i53]Deeparnab Chakrabarty, Maryam Negahbani:
Better Algorithms for Individually Fair k-Clustering. CoRR abs/2106.12150 (2021) - [i52]Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna:
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection. CoRR abs/2111.07474 (2021) - 2020
- [j25]Sayan Bhattacharya
Deterministic Dynamic Matching in O(1) Update Time. Algorithmica 82(4): 1057-1080 (2020) - [j24]Deeparnab Chakrabarty, Prachi Goyal, Ravishankar Krishnaswamy:
The Non-Uniform k-Center Problem. ACM Trans. Algorithms 16(4): 46:1-46:19 (2020) - [j23]Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. Theory Comput. 16: 1-36 (2020) - [c48]Deeparnab Chakrabarty, Paul de Supinski:
On a Decentralized (Δ+1)-Graph Coloring Algorithm. SOSA 2020: 91-98 - [c47]Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions. SODA 2020: 1975-1994 - [i51]Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna:
Graph Connectivity and Single Element Recovery via Linear and OR Queries. CoRR abs/2007.06098 (2020)
2010 – 2019
- 2019
- [j22]Deeparnab Chakrabarty, Maryam Negahbani:
Generalized Center Problems with Outliers. ACM Trans. Algorithms 15(3): 41:1-41:14 (2019) - [c46]Deeparnab Chakrabarty, Chaitanya Swamy:
Simpler and Better Algorithms for Minimum-Norm Load Balancing. ESA 2019: 27:1-27:12 - [c45]Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, Sam Chiu-wai Wong:
Faster Matroid Intersection. FOCS 2019: 1146-1168 - [c44]Deeparnab Chakrabarty, C. Seshadhri:
Adaptive Boolean Monotonicity Testing in Total Influence Time. ITCS 2019: 20:1-20:7 - [c43]Suman Kalyan Bera, Deeparnab Chakrabarty, Nicolas Flores, Maryam Negahbani:
Fair Algorithms for Clustering. NeurIPS 2019: 4955-4966 - [c42]Deeparnab Chakrabarty, Chaitanya Swamy:
Approximation algorithms for minimum norm and ordered optimization problems. STOC 2019: 126-137 - [i50]Suman K. Bera, Deeparnab Chakrabarty, Maryam Negahbani:
Fair Algorithms for Clustering. CoRR abs/1901.02393 (2019) - [i49]Deeparnab Chakrabarty, Chaitanya Swamy:
Simpler and Better Algorithms for Minimum-Norm Load Balancing. CoRR abs/1905.00044 (2019) - [i48]Deeparnab Chakrabarty, Paul de Supinski:
On a Decentralized (Δ{+}1)-Graph Coloring Algorithm. CoRR abs/1910.13900 (2019) - [i47]Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, Sam Chiu-wai Wong:
Faster Matroid Intersection. CoRR abs/1911.10765 (2019) - 2018
- [j21]Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy, Debmalya Panigrahi:
Online Buy-at-Bulk Network Design. SIAM J. Comput. 47(4): 1505-1528 (2018) - [c41]Deeparnab Chakrabarty, Chaitanya Swamy:
Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median. ICALP 2018: 29:1-29:14 - [c40]Deeparnab Chakrabarty, Maryam Negahbani:
Generalized Center Problems with Outliers. ICALP 2018: 30:1-30:14 - [c39]Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger
Dynamic Algorithms for Graph Coloring. SODA 2018: 1-20 - [c38]Deeparnab Chakrabarty, Sanjeev Khanna:
Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling. SOSA 2018: 4:1-4:11 - [c37]Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
A o(d) · polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]d. SODA 2018: 2133-2151 - [i46]Deeparnab Chakrabarty, Sanjeev Khanna:
Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling. CoRR abs/1801.02790 (2018) - [i45]Deeparnab Chakrabarty, C. Seshadhri:
Adaptive Boolean Monotonicity Testing in Total Influence Time. CoRR abs/1801.02816 (2018) - [i44]Deeparnab Chakrabarty, Maryam Negahbani:
Generalized Center Problems with Outliers. CoRR abs/1805.02217 (2018) - [i43]Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions on Hypergrids. CoRR abs/1811.01427 (2018) - [i42]Deeparnab Chakrabarty, Chaitanya Swamy:
Approximation Algorithms for Minimum Norm and Ordered Optimization Problems. CoRR abs/1811.05022 (2018) - [i41]Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions on Hypergrids. Electron. Colloquium Comput. Complex. TR18 (2018) - [i40]Deeparnab Chakrabarty, C. Seshadhri:
Adaptive Boolean Monotonicity Testing in Total Influence Time. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j20]Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, C. Seshadhri:
Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties. ACM Trans. Algorithms 13(2): 20:1-20:30 (2017) - [c36]Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. ICALP 2017: 5:1-5:14 - [c35]Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger:
Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time. IPCO 2017: 86-98 - [c34]Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Amit Kumar
The Heterogeneous Capacitated k-Center Problem. IPCO 2017: 123-135 - [c33]Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong:
Subquadratic submodular function minimization. STOC 2017: 1220-1231 - [i39]Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri:
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. CoRR abs/1703.05199 (2017) - [i38]Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri:
A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube. CoRR abs/1706.00053 (2017) - [i37]Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
A $o(d) \cdot \text{polylog}~n$ Monotonicity Tester for Boolean Functions over the Hypergrid [n]d. CoRR abs/1710.10545 (2017) - [i36]Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, Danupon Nanongkai:
Dynamic Algorithms for Graph Coloring. CoRR abs/1711.04355 (2017) - [i35]Deeparnab Chakrabarty, Chaitanya Swamy:
Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median. CoRR abs/1711.08715 (2017) - [i34]Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri:
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. Electron. Colloquium Comput. Complex. TR17 (2017) - [i33]Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri:
A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube. Electron. Colloquium Comput. Complex. TR17 (2017) - [i32]Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
A o(d) · polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]d. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j19]Deeparnab Chakrabarty, Sampath Kannan, Kevin Tian:
Detecting Character Dependencies in Stochastic Models of Evolution. J. Comput. Biol. 23(3): 180-191 (2016) - [j18]Deeparnab Chakrabarty, Chaitanya Swamy:
Facility Location with Client Latencies: LP-Based Techniques for Minimum-Latency Problems. Math. Oper. Res. 41(3): 865-883 (2016) - [j17]Deeparnab Chakrabarty, C. Seshadhri:
An o(n) Monotonicity Tester for Boolean Functions over the Hypercube. SIAM J. Comput. 45(2): 461-472 (2016) - [j16]Deeparnab Chakrabarty, David J. Galvin:
Special Issue: APPROX-RANDOM 2014: Guest Editors' Foreword. Theory Comput. 12(1): 1-3 (2016) - [c32]Deeparnab Chakrabarty, Prachi Goyal, Ravishankar Krishnaswamy:
The Non-Uniform k-Center Problem. ICALP 2016: 67:1-67:15 - [c31]Apurv Bhartia, Deeparnab Chakrabarty, Krishna Chintalapudi, Lili Qiu, Bozidar Radunovic, Ramachandran Ramjee:
IQ-Hopping: distributed oblivious channel selection for wireless networks. MobiHoc 2016: 81-90 - [r2]Deeparnab Chakrabarty:
Max-Min Allocation. Encyclopedia of Algorithms 2016: 1244-1247 - [r1]Deeparnab Chakrabarty:
Monotonicity Testing. Encyclopedia of Algorithms 2016: 1352-1356 - [i31]Deeparnab Chakrabarty, Kirankumar Shiragur:
Graph Balancing with Two Edge Types. CoRR abs/1604.06918 (2016) - [i30]Deeparnab Chakrabarty, Prachi Goyal, Ravishankar Krishnaswamy:
The Non-Uniform k-Center Problem. CoRR abs/1605.03692 (2016) - [i29]Deeparnab Chakrabarty, C. Seshadhri:
A $\widetilde{O}(n)$ Non-Adaptive Tester for Unateness. CoRR abs/1608.06980 (2016) - [i28]Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong:
Subquadratic Submodular Function Minimization. CoRR abs/1610.09800 (2016) - [i27]Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger:
Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in $O(1)$ Amortized Update Time. CoRR abs/1611.00198 (2016) - [i26]Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Amit Kumar:
The Heterogeneous Capacitated $k$-Center Problem. CoRR abs/1611.07414 (2016) - [i25]Deeparnab Chakrabarty, C. Seshadhri:
A Õ(n) Non-Adaptive Tester for Unateness. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j15]Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula:
Approximability of Capacitated Network Design. Algorithmica 72(2): 493-514 (2015) - [j14]Deeparnab Chakrabarty, Zhiyi Huang
Recognizing Coverage Functions. SIAM J. Discret. Math. 29(3): 1585-1599 (2015) - [c30]Alina Ene, Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Debmalya Panigrahi:
Online Buy-at-Bulk Network Design. FOCS 2015: 545-562 - [c29]Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li:
On (1, ∊)-Restricted Assignment Makespan Minimization. SODA 2015: 1087-1101 - [c28]Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, C. Seshadhri:
Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties. SODA 2015: 1809-1828 - [i24]Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy, Debmalya Panigrahi:
Online Buy-at-Bulk Network Design. CoRR abs/1509.03212 (2015) - 2014
- [j13]Deeparnab Chakrabarty, Gagan Goel, Vijay V. Vazirani, Lei Wang, Changyuan Yu:
Submodularity Helps in Nash and Nonsymmetric Bargaining Games. SIAM J. Discret. Math. 28(1): 99-115 (2014) - [j12]Deeparnab Chakrabarty, C. Seshadhri:
An Optimal Lower Bound for Monotonicity Testing over Hypergrids. Theory Comput. 10: 453-464 (2014) - [c27]Deeparnab Chakrabarty, Chaitanya Swamy:
Welfare maximization and truthfulness in mechanism design with ordinal preferences. ITCS 2014: 105-120 - [c26]Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari:
Provable Submodular Minimization using Wolfe's Algorithm. NIPS 2014: 802-809 - [i23]Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, C. Seshadhri:
Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties. CoRR abs/1404.0718 (2014) - [i22]Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li:
On $(1, ε)$-Restricted Assignment Makespan Minimization. CoRR abs/1410.7506 (2014) - [i21]Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari:
Provable Submodular Minimization using Wolfe's Algorithm. CoRR abs/1411.0095 (2014) - [i20]Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, C. Seshadhri:
Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j11]Deeparnab Chakrabarty, Jochen Könemann, David Pritchard:
Hypergraphic LP Relaxations for Steiner Trees. SIAM J. Discret. Math. 27(1): 507-533 (2013) - [c25]Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Shi Li, Srivatsan Narayanan:
Capacitated Network Design on Undirected Graphs. APPROX-RANDOM 2013: 71-80 - [c24]Deeparnab Chakrabarty, C. Seshadhri:
An Optimal Lower Bound for Monotonicity Testing over Hypergrids. APPROX-RANDOM 2013: 425-435 - [c23]Denis Xavier Charles, Deeparnab Chakrabarty, Max Chickering, Nikhil R. Devanur, Lei Wang:
Budget smoothing for internet ad auctions: a game theoretic approach. EC 2013: 163-180 - [c22]Deeparnab Chakrabarty, C. Seshadhri:
A o(n) monotonicity tester for boolean functions over the hypercube. STOC 2013: 411-418 - [c21]Deeparnab Chakrabarty, C. Seshadhri:
Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids. STOC 2013: 419-428 - [i19]Deeparnab Chakrabarty, C. Seshadhri:
A o(n) monotonicity tester for Boolean functions over the hypercube. CoRR abs/1302.4536 (2013) - [i18]Deeparnab Chakrabarty, C. Seshadhri:
An optimal lower bound for monotonicity testing over hypergrids. CoRR abs/1304.5264 (2013) - [i17]Deeparnab Chakrabarty, Chaitanya Swamy:
Welfare Maximization and Truthfulness in Mechanism Design with Ordinal Preferences. CoRR abs/1312.1831 (2013) - [i16]Deeparnab Chakrabarty, C. Seshadhri:
A o(n) monotonicity tester for Boolean functions over the hypercube. Electron. Colloquium Comput. Complex. TR13 (2013) - [i15]Deeparnab Chakrabarty, C. Seshadhri:
An optimal lower bound for monotonicity testing over hypergrids. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j10]Elliot Anshelevich
Approximability of the Firefighter Problem - Computing Cuts over Time. Algorithmica 62(1-2): 520-536 (2012) - [j9]Deeparnab Chakrabarty:
Review of design of approximation algorithms, by David P. Williamson and David B. Shmoys. SIGACT News 43(4): 52-54 (2012) - [c20]Deeparnab Chakrabarty, Zhiyi Huang:
Testing Coverage Functions. ICALP (1) 2012: 170-181 - [i14]Deeparnab Chakrabarty, C. Seshadhri:
Optimal bounds for monotonicity and Lipschitz testing over the hypercube. CoRR abs/1204.0849 (2012) - [i13]Deeparnab Chakrabarty, Zhiyi Huang:
Testing Coverage Functions. CoRR abs/1205.1587 (2012) - [i12]Deeparnab Chakrabarty, C. Seshadhri:
Optimal bounds for monotonicity and Lipschitz testing over the hypercube. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j8]David Pritchard, Deeparnab Chakrabarty:
Approximability of Sparse Integer Programs. Algorithmica 61(1): 75-93 (2011) - [j7]Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani:
New geometry-inspired relaxations and algorithms for the metric Steiner tree problem. Math. Program. 130(1): 1-32 (2011) - [c19]Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna:
Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs. APPROX-RANDOM 2011: 75-86 - [c18]Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna:
Social Welfare in One-Sided Matching Markets without Money. APPROX-RANDOM 2011: 87-98 - [c17]Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula:
Approximability of Capacitated Network Design. IPCO 2011: 78-91 - [c16]Deeparnab Chakrabarty, Chaitanya Swamy:
Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems. IPCO 2011: 92-103 - [i11]Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna:
Social Welfare in One-sided Matching Markets without Money. CoRR abs/1104.2964 (2011) - [i10]Deeparnab Chakrabarty, Sampath Kannan:
Variance on the Leaves of a Tree Markov Random Field: Detecting Character Dependencies in Phylogenies. CoRR abs/1112.5508 (2011) - 2010
- [j6]Brian Benson, Deeparnab Chakrabarty, Prasad Tetali:
G-parking functions, acyclic orientations and spanning trees. Discret. Math. 310(8): 1340-1353 (2010) - [j5]Deeparnab Chakrabarty, Jochen Könemann, David Pritchard:
Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound. Oper. Res. Lett. 38(6): 567-570 (2010) - [j4]Deeparnab Chakrabarty, Gagan Goel:
On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP. SIAM J. Comput. 39(6): 2189-2211 (2010) - [j3]Deeparnab Chakrabarty, Aranyak Mehta, Vijay V. Vazirani:
Design is as Easy as Optimization. SIAM J. Discret. Math. 24(1): 270-286 (2010) - [j2]Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani:
Rationality and Strongly Polynomial Solvability of Eisenberg--Gale Markets with Two Agents. SIAM J. Discret. Math. 24(3): 1117-1136 (2010) - [c15]Deeparnab Chakrabarty, Elyot Grant, Jochen Könemann:
On Column-Restricted and Priority Covering Integer Programs. IPCO 2010: 355-368 - [c14]Deeparnab Chakrabarty, Jochen Könemann, David Pritchard:
Hypergraphic LP Relaxations for Steiner Trees. IPCO 2010: 383-396 - [i9]Deeparnab Chakrabarty, Elyot Grant, Jochen Könemann:
On Column-restricted and Priority Covering Integer Programs. CoRR abs/1003.1507 (2010) - [i8]Deeparnab Chakrabarty, Jochen Könemann, David Pritchard:
Integrality Gap of the Hypergraphic Relaxation of Steiner Trees: a short proof of a 1.55 upper bound. CoRR abs/1006.2249 (2010) - [i7]Deeparnab Chakrabarty, Chaitanya Swamy:
Facility Location with Client Latencies: Linear-Programming based Techniques for Minimum-Latency Problems. CoRR abs/1009.2452 (2010) - [i6]Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula:
Approximability of Capacitated Network Design. CoRR abs/1009.5734 (2010) - [i5]Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna:
Optimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSP. CoRR abs/1011.3770 (2010)
2000 – 2009
- 2009
- [j1]Deeparnab Chakrabarty, Nikhil R. Devanur:
On competitiveness in uniform utility allocation markets. Oper. Res. Lett. 37(3): 155-158 (2009) - [c13]Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna:
On Allocating Goods to Maximize Fairness. FOCS 2009: 107-116 - [c12]Mostafa H. Ammar, Deeparnab Chakrabarty, Atish Das Sarma, Subrahmanyam Kalyanasundaram
Algorithms for Message Ferrying on Mobile ad hoc Networks. FSTTCS 2009: 13-24 - [c11]Elliot Anshelevich
Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity. ISAAC 2009: 974-983 - [i4]Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna:
On Allocating Goods to Maximize Fairness. CoRR abs/0901.0205 (2009) - [i3]Deeparnab Chakrabarty, Jochen Könemann, David Pritchard:
Hypergraphic LP Relaxations for Steiner Trees. CoRR abs/0910.0281 (2009) - [i2]Deeparnab Chakrabarty, Chinmay Karande, Ashish Sangwan:
The Effect of Malice on the Social Optimum in Linear Load Balancing Games. CoRR abs/0910.2655 (2009) - 2008
- [b1]Deeparnab Chakrabarty:
Algorithmic aspects of connectivity, allocation and design problems. Georgia Institute of Technology, Atlanta, GA, USA, 2008 - [c10]Deeparnab Chakrabarty, Gagan Goel:
On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP. FOCS 2008: 687-696 - [c9]Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani:
New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem. IPCO 2008: 344-358 - [c8]Deeparnab Chakrabarty, Gagan Goel, Vijay V. Vazirani, Lei Wang, Changyuan Yu:
Efficiency, Fairness and Competitiveness in Nash Bargaining Games. WINE 2008: 498-505 - [c7]Yunhong Zhou, Deeparnab Chakrabarty, Rajan M. Lukose:
Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems. WINE 2008: 566-576 - [c6]Yunhong Zhou, Deeparnab Chakrabarty, Rajan M. Lukose:
Budget constrained bidding in keyword auctions and online knapsack problems. WWW 2008: 1243-1244 - 2007
- [c5]Deeparnab Chakrabarty, Nikhil R. Devanur:
On Competitiveness in Uniform Utility Allocation Markets. WINE 2007: 374-380 - [c4]Atish Das Sarma, Deeparnab Chakrabarty, Sreenivas Gollapudi:
Public Advertisement Broker Markets. WINE 2007: 558-563 - 2006
- [c3]Deeparnab Chakrabarty, Aranyak Mehta, Vijay V. Vazirani:
Design Is as Easy as Optimization. ICALP (1) 2006: 477-488 - [c2]Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani:
New Results on Rationality and Strongly Polynomial Time Solvability in Eisenberg-Gale Markets. WINE 2006: 239-250 - [i1]Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani:
Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [c1]Deeparnab Chakrabarty, Aranyak Mehta, Viswanath Nagarajan:
Fairness and optimality in congestion games. EC 2005: 52-57
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-08 02:26 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: