Anupam Sen Gupta
#165,785
Most Influential Person Now
Anupam Sen Gupta's AcademicInfluence.com Rankings
Anupam Sen Guptamathematics Degrees
Mathematics
#7512
World Rank
#10201
Historical Rank
Measure Theory
#2239
World Rank
#2688
Historical Rank

Anupam Sen Guptacomputer-science Degrees
Computer Science
#9925
World Rank
#10412
Historical Rank
Theoretical Computer Science
#116
World Rank
#116
Historical Rank

Download Badge
Mathematics Computer Science
Anupam Sen Gupta's Degrees
- Bachelors Mathematics University of Calcutta
Similar Degrees You Can Earn
Why Is Anupam Sen Gupta Influential?
(Suggest an Edit or Addition)Anupam Sen Gupta's Published Works
Number of citations in a given year to any of this author's works
Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author
Published Works
- An elementary proof of a theorem of Johnson and Lindenstrauss (2003) (957)
- Bounded geometries, fractals, and low-distortion embeddings (2003) (425)
- An elementary proof of the Johnson-Lindenstrauss Lemma (1999) (412)
- Provisioning a virtual private network: a network design problem for multicommodity flow (2001) (302)
- Robust Submodular Observation Selection (2008) (287)
- Iterative Constructions and Private Data Release (2011) (201)
- Simpler and better approximation algorithms for network design (2003) (200)
- Differentially private combinatorial optimization (2009) (185)
- Boosted sampling: approximation algorithms for stochastic optimization (2004) (178)
- Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms (2010) (178)
- Cuts, Trees and ℓ1-Embeddings of Graphs* (1999) (171)
- Privately releasing conjunctions and the statistical query barrier (2010) (153)
- Approximate clustering without the approximation (2009) (144)
- Approximation Algorithms for the Unsplittable Flow Problem (2002) (143)
- On hierarchical routing in doubling metrics (2005) (137)
- When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings (2010) (133)
- Forest Density Estimation (2010) (121)
- Better Algorithms for Stochastic Bandits with Adversarial Corruptions (2019) (109)
- Discovering pathways by orienting edges in protein interaction networks (2010) (103)
- Steiner points in tree metrics don't (really) help (2001) (101)
- Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut (2005) (97)
- Oblivious network design (2006) (92)
- Simpler Analyses of Local Search Algorithms for Facility Location (2008) (90)
- A Stochastic Probing Problem with Applications (2013) (89)
- Approximation algorithms for low-distortion embeddings into low-dimensional spaces (2005) (85)
- An edge in time saves nine: LP rounding approximation algorithms for stochastic network design (2004) (83)
- Set connectivity problems in undirected graphs and the directed Steiner network problem (2008) (83)
- Secretary problems: weights and discounts (2009) (82)
- Metric embeddings with relaxed guarantees (2005) (82)
- Clustering under approximation stability (2013) (77)
- Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling (2011) (77)
- Simultaneous placement and scheduling of sensors (2009) (76)
- Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits (2011) (75)
- Cost-Sharing Mechanisms for Network Design (2007) (75)
- Online and dynamic algorithms for set cover (2016) (72)
- ALICE technical design report on forward detectors: FMD, T0 and V0 (2004) (71)
- Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem (2003) (70)
- Stochastic analyses for online combinatorial optimization problems (2008) (69)
- Vertex Sparsifiers: New Results from Old Techniques (2010) (69)
- On the approximability of some network design problems (2005) (68)
- A constant-factor approximation algorithm for the multicommodity rent-or-buy problem (2002) (67)
- Traveling with a Pez dispenser (or, routing issues in MPLS) (2001) (66)
- Embedding k-outerplanar graphs into ℓ1 (2003) (65)
- Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions (2016) (64)
- Scheduling heterogeneous processors isn't as easy as you think (2012) (64)
- What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization (2005) (61)
- Lower bounds for embedding edit distance into normed spaces (2003) (60)
- A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs (2015) (59)
- Simultaneous Optimization of Sensor Placements and Balanced Schedules (2011) (59)
- Algorithms and Adaptivity Gaps for Stochastic Probing (2016) (58)
- Online Algorithms for Covering and Packing Problems with Convex Objectives (2016) (58)
- Embedding Tree Metrics into Low-Dimensional Euclidean Spaces (1999) (58)
- Improved results for directed multicut (2003) (57)
- Approximating unique games (2006) (57)
- Robust sensor placements at informative and communication-efficient locations (2011) (55)
- Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems (2010) (55)
- Approximation algorithms for network design: A survey (2011) (55)
- Approximation algorithms for stochastic orienteering (2012) (55)
- Counting inversions in lists (2003) (55)
- Maintaining Assignments Online: Matching, Scheduling, and Flows (2014) (52)
- Welfare and Profit Maximization with Production Costs (2011) (52)
- A constant factor approximation algorithm for a class of classification problems (2000) (52)
- A constant factor approximation algorithm for generalized min-sum set cover (2010) (52)
- The power of deferral: maintaining a constant-competitive steiner tree online (2013) (50)
- Small Hop-diameter Sparse Spanners for Doubling Metrics (2006) (47)
- Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs (2013) (47)
- A Randomized O(log2k)-Competitive Algorithm for Metric Bipartite Matching (2014) (46)
- Dial a Ride from k-forest (2007) (46)
- Approximation via cost sharing (2007) (46)
- Selecting Observations against Adversarial Objectives (2007) (46)
- Scalably Scheduling Power-Heterogeneous Processors (2010) (45)
- Spanners with Slack (2006) (45)
- How the Experts Algorithm Can Help Solve LPs Online (2014) (45)
- Nearly-Linear Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs (2011) (43)
- Sorting and selection with structured costs (2001) (42)
- Tight FPT Approximations for $k$-Median and k-Means (2019) (42)
- An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem (2007) (42)
- Chasing Convex Bodies with Linear Competitive Ratio (2019) (41)
- Extracting Dynamics from Static Cancer Expression Data (2008) (40)
- The Online Metric Matching Problem for Doubling Metrics (2012) (40)
- Pure Exploration of Multi-armed Bandit Under Matroid Constraints (2016) (40)
- Changing Bases: Multistage Optimization for Matroids and Matchings (2014) (40)
- Network-wide deployment of intrusion detection and prevention systems (2010) (39)
- Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration (2017) (38)
- Exploring the trade-off between label size and stack depth in MPLS routing (2003) (37)
- Potential-Function Proofs for Gradient Methods (2019) (37)
- Stochastic Steiner Trees Without a Root (2005) (36)
- Scheduling jobs with varying parallelizability to reduce variance (2010) (36)
- Set Covering with our Eyes Closed (2008) (36)
- Infrastructure Leasing Problems (2007) (36)
- Harnessing the power of two crossmatches (2013) (36)
- Towards (1 + ∊)-Approximate Flow Sparsifiers (2013) (35)
- Sparsest cut on bounded treewidth graphs: algorithms and hardness results (2013) (34)
- Thresholded covering algorithms for robust and max–min optimization (2009) (34)
- Online and stochastic survivable network design (2009) (33)
- Technical Note - Approximation Algorithms for VRP with Stochastic Demands (2012) (33)
- Online Steiner Tree with Deletions (2013) (32)
- An O (log2 k )-Competitive Algorithm for Metric Bipartite Matching (2007) (30)
- Potential-Function Proofs for First-Order Methods (2017) (29)
- Running Errands in Time: Approximation Algorithms for Stochastic Orienteering (2015) (27)
- Packing Interdiction and Partial Covering Problems (2013) (27)
- Approximating Sparse Covering Integer Programs Online (2012) (27)
- Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets (2010) (27)
- Sampling and Cost-Sharing: Approximation Algorithms for Stochastic Optimization Problems (2011) (27)
- Fair algorithms for selecting citizens’ assemblies (2021) (26)
- Differentially Private Approximation Algorithms (2009) (25)
- On the Lovász Theta function for Independent Sets in Sparse Graphs (2015) (25)
- A Nearly-Linear Bound for Chasing Nested Convex Bodies (2018) (25)
- An FPT Algorithm Beating 2-Approximation for k-Cut (2017) (24)
- A Plant Location Guide for the Unsure: Approximation Algorithms for Min-Max Location Problems (2010) (24)
- Faster Exact and Approximate Algorithms for k-Cut (2018) (24)
- Algorithms for Hub Label Optimization (2013) (24)
- Improved Bandwidth Approximation for Trees and Chordal Graphs (2001) (24)
- The Online Submodular Cover Problem (2020) (23)
- All-Norms and All-L_p-Norms Approximation Algorithms (2008) (23)
- Losing Treewidth by Separating Subsets (2018) (23)
- Steiner Point Removal in Graph Metrics (2008) (23)
- An improved approximation algorithm for requirement cut (2010) (23)
- How Experts Can Solve LPs Online (2014) (22)
- Quorum placement in networks to minimize access delays (2005) (22)
- Nonclairvoyantly scheduling power-heterogeneous processors (2010) (21)
- Building Edge-Failure Resilient Networks (2002) (21)
- Greedy Algorithms for Steiner Forest (2014) (21)
- Fully-Dynamic Bin Packing with Little Repacking (2018) (21)
- k-Servers with a Smile: Online Algorithms via Projections (2018) (21)
- Nearly-Linear Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs (2011) (19)
- The Markovian Price of Information (2019) (18)
- Tree embeddings for two-edge-connected network design (2010) (18)
- ALICE Technical Design Report of the Computing (2005) (17)
- Online Packing and Covering Framework with Convex Objectives (2014) (17)
- Scheduling with Outliers (2009) (17)
- Stochastic Load Balancing on Unrelated Machines (2018) (17)
- Approximation Algorithms for Minimizing Average Distortion (2004) (16)
- Robust Algorithms for the Secretary Problem (2019) (16)
- Stochastic Steiner Tree with Non-uniform Inflation (2007) (15)
- Approximating TSP on metrics with bounded global growth (2008) (15)
- Improved embeddings of graph metrics into random trees (2006) (14)
- Metric embedding via shortest path decompositions (2017) (14)
- Neutralizing Self-Selection Bias in Sampling for Sortition (2020) (14)
- Parallel probabilistic tree embeddings, k-median, and buy-at-bulk network design (2012) (14)
- A plant location guide for the unsure (2008) (13)
- A constant-factor approximation for stochastic Steiner forest (2009) (13)
- Ultra-low-dimensional embeddings for doubling metrics (2008) (13)
- When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings (2010) (13)
- Quorum placement in networks: minimizing network congestion (2006) (13)
- A Local-Search Algorithm for Steiner Forest (2017) (12)
- Stochastic Online Metric Matching (2019) (12)
- Coordinated sampling sans Origin-Destination identifiers: Algorithms and analysis (2010) (12)
- Multicast Routing for Energy Minimization Using Speed Scaling (2012) (11)
- The number of minimum k-cuts: improving the Karger-Stein bound (2019) (11)
- Embeddings of finite metrics (2000) (11)
- Elastic Caching (2019) (11)
- Approximation Algorithms for VRP with Stochastic Demands (2012) (11)
- LAST but not Least: Online Spanners for Buy-at-Bulk (2016) (11)
- The Karger-Stein algorithm is optimal for k-cut (2019) (10)
- Improved bandwidth approximation for trees (2000) (10)
- Fully-Dynamic Submodular Cover with Bounded Recourse (2020) (10)
- Tree based MPLS routing (2003) (10)
- Distributed caching algorirthms for content distribution netowkrs (2010) (10)
- Structural Iterative Rounding for Generalized k-Median Problems (2020) (9)
- An Improved Integrality Gap for Asymmetric TSP Paths (2013) (9)
- On the Covering Steiner Problem (2003) (9)
- An Improved Approximation Ratio for the Covering Steiner Problem (2006) (8)
- Fully-Dynamic Bin Packing with Limited Repacking (2017) (8)
- Optimal Bounds for the k-cut Problem (2020) (8)
- Caching with time windows (2020) (8)
- When LP is the Cure for Your Matching Woes: Approximating Stochastic Matchings (2010) (8)
- An Improved Local Search Algorithm for k-Median (2021) (6)
- Dial a Ride from k -Forest (2007) (6)
- Maximizing Profit with Convex Costs in the Random-order Model (2018) (6)
- Dimension-Free Bounds on Chasing Convex Functions (2020) (6)
- Non-clairvoyant Precedence Constrained Scheduling (2019) (6)
- On the Approximability of Network Design Problems (2005) (6)
- Where's the Winner? Max-Finding and Sorting with Metric Costs (2005) (6)
- Efficient parallel approximation algorithms (2011) (6)
- The Power of Adaptivity for Stochastic Submodular Cover (2021) (5)
- The Approximability of the Binary Paintshop Problem (2013) (5)
- Losing tree-width by separating subsets (2019) (5)
- Efficient cost-sharing mechanisms for prize-collecting problems (2015) (4)
- Random Rates for 0-Extension and Low-Diameter Decompositions (2013) (4)
- Pricing Tree Access Networks with Connected Backbones (2007) (4)
- Matroid-Based TSP Rounding for Half-Integral Solutions (2021) (4)
- A Randomized O(log2k)-Competitive Algorithm for Metric Bipartite Matching (2012) (4)
- Stochastic makespan minimization in structured set systems (2020) (4)
- Approximation Algorithms for Aversion k-Clustering via Local k-Median (2016) (4)
- Non-Adaptive Stochastic Score Classification and Explainable Halfspace Evaluation (2021) (4)
- The Connectivity Threshold for Dense Graphs (2021) (3)
- A Hitting Set Relaxation for $k$-Server and an Extension to Time-Windows (2021) (3)
- Random Order Online Set Cover is as Easy as Offline (2022) (3)
- Some Efficient Solutions to Yao's Millionaire Problem (2013) (3)
- Set connectivity problems in undirected graphs and the directed steiner network problem (2011) (3)
- On the E ciency of Restricted Tolls in Network Routing Games (2010) (3)
- Towards (1+\epsilon)-Approximate Flow Sparsifiers (2013) (3)
- Robust Secretary and Prophet Algorithms for Packing Integer Programs (2021) (3)
- Making Doubling Metrics Geodesic (2010) (3)
- Coordinated Sampling sans Origin-Destination Identifiers : Algorithms , Analysis , and Evaluation (2009) (2)
- How to Complete a Doubling Metric (2007) (2)
- Thresholded covering algorithms for robust and max–min optimization (2013) (2)
- Chasing convex bodies with linear competitive ratio (invited paper) (2021) (2)
- Running Errands in Time: Approximation Algorithms for (2015) (2)
- Online Discrepancy with Recourse for Vectors and Graphs (2021) (2)
- A quasipolynomial (2 + ε)-approximation for planar sparsest cut (2021) (2)
- Catch them if you can: how to serve impatient users (2013) (2)
- Online Carpooling using Expander Decompositions (2020) (2)
- Lecture notes for CMU’s course on Linear Programming & Semidefinite Programming (2011) (2)
- On Configuring BGP Route Reflectors (2007) (2)
- Approximation, randomization and combinatorial optimization : algorithms and techniques : 15th International Workshop, APPROX 2012 and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012 : proceedings (2012) (2)
- The Price of Explainability for Clustering (2023) (1)
- Lecture 5: Primal-Dual Algorithms and Facility Location (2008) (1)
- Thrifty Algorithms for Multistage Robust Optimization (2013) (1)
- A Quasipolynomial $(2+\varepsilon)$-Approximation for Planar Sparsest Cut (2021) (1)
- Probing to Minimize (2021) (1)
- Random Order Set Cover is as Easy as Offline (2021) (1)
- Learning from a Sample in Online Algorithms (2022) (1)
- A Novel System Defined Network Solution for User Legitimacy Assurance in the Docker Containers (2018) (1)
- Non-Preemptive Flow-Time Minimization via Rejections (2018) (1)
- Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract) (2020) (1)
- Caching with Time Windows and Delays (2020) (1)
- On a bidirected relaxation for the MULTIWAY CUT problem (2005) (1)
- Stochastic Unsplittable Flows (2017) (1)
- Constrained Maximization of Non-Monotone Submodular Functions (2009) (0)
- 5.1 Introduction (0)
- Fast Algorithms for Proximity Search on Large Graphs Purnamrita (2008) (0)
- Title Metric embeddings with relaxed guarantees (2009) (0)
- 23.1 Improving Convex Programming Relaxations (2005) (0)
- Lecture 6: Facility location: greedy and local search algorithms 31-Jan-08 (2008) (0)
- Stochastic Analysis of Online Algorithms (2007) (0)
- 7.1 Introduction 7.2 Weighted Max Cut (2007) (0)
- Lecture 27: Algorithms for Sparsest Cut (2008) (0)
- Session details: Session 11B (2005) (0)
- Chapter-05 Nausea and Vomiting (2014) (0)
- 3 . 1 Greedy Algorithm for Approximating Set Cover • Greedy Algorithm (2018) (0)
- Algorithms for Uncertain Environments: Going Beyond the Worst-Case (Invited Talk) (2022) (0)
- Note on Bounded Degree Spanners for Doubling Metrics (2007) (0)
- Bag-of-Tasks Scheduling on Related Machines (2021) (0)
- Set Covering with Our Eyes Wide Shut (2023) (0)
- Augmenting Online Algorithms with $\varepsilon$-Accurate Predictions (2022) (0)
- Approximation algorithms for network design with uncertainty (2008) (0)
- Configuration Balancing for Stochastic Requests (2022) (0)
- Experimental study on the join forsterite-albite-anorthite at 35 kbar and its significance on the upper mantle petrology : Experimental petrology (1993) (0)
- A Local Search-Based Approach for Set Covering (2022) (0)
- POWER EFFICIENT TASK SCHEDULING MECHANISM IN CLOUD ENVIRONMENT: A REVIEW (2016) (0)
- Solving Flow Problems using Multiplicative Weights (2015) (0)
- D S ] 2 3 O ct 2 01 8 Losing Treewidth by Separating Subsets (2018) (0)
- Steiner Tree with Deletions Anupam Gupta (2015) (0)
- Lipschitz Selectors may not Yield Competitive Algorithms for Convex Body Chasing (2021) (0)
- Session details: 10A (2008) (0)
- Minimizing Completion Times for Stochastic Jobs via Batched Free Times (2022) (0)
- Case Study: NBL Team Anthem, WWF India (2009) (0)
- 10211 Abstracts Collection - Flexible Network Design (2010) (0)
- Steiner Tree with Deletions (2013) (0)
- 6-2007 Infrastructure Leasing Problems (2015) (0)
- On Hierarchical Routing in Doubling Metrics (CMU-PDL-04-106) (2004) (0)
- Lecture 4: Uncapacitated Facility Location (2008) (0)
- Advanced Approximation Algorithms ( CMU 15-854 B , Spring 2008 ) Lecture 10 : Group Steiner Tree problem 14 (2008) (0)
- Special Issue Dedicated to the Thirty-Seventh Annual ACM Symposium on Theory of Computing (STOC 2005) (2008) (0)
- Advanced Approximation Algorithms (cmu 15-854b, Spring 2008) 1 Integrality Gap 1.1 Lp Relaxation (2008) (0)
- Stochastic Unsplittable Flow Problem ( sUFP ) on Directed Acyclic Graphs (2017) (0)
- Matrix Multiplication Checking (2011) (0)
- Minimum d-dimensional arrangement with fixed points (2013) (0)
- Technical Note Approximation Algorithms for VRP with (2012) (0)
- Online Learning and Competitive Analysis: a Unified Approach (2015) (0)
- 5.1 Introduction 5.2 a Randomized Algorithm (0)
- 15-859 FF : Coping with Intractability (2019) (0)
- .1 Introduction 1.2 Why Randomized Algorithms (2004) (0)
- 2 The Ski Rental Problem : Rent or Buy ? (2018) (0)
- Lecture 7: Asymmetric K-Center (2007) (0)
- Tepper School of Business 4-19-2005 Approximation Algorithms for Minimizing Average Distortion (2015) (0)
- Session details: 3B (2008) (0)
- Session details: Session 4B (2005) (0)
- Super scalar high speed 2(mew) N-well MOSIS CMOS digital halftoning processor (1996) (0)
- 2 Norms and their Duals (2017) (0)
- Stochastic makespan minimization in structured set systems (2021) (0)
- Finishing up Group Steiner Tree Hardness 2 Steiner Tree (2008) (0)
- Lecturer: Anupam Gupta (2008) (0)
- Advanced Approximation Algorithms ( CMU 15-854 B , Spring 2008 ) Lecture 20 : Embeddings into Trees and L 1 Embeddings March 27 2008 (2008) (0)
- SURVEY Potential-Function Proofs for Gradient Methods (2019) (0)
This paper list is powered by the following services:
What Schools Are Affiliated With Anupam Sen Gupta?
Anupam Sen Gupta is affiliated with the following schools: