David P. Williamson | Academic Influence

David P. Williamson's AcademicInfluence.com Rankings

David P. Williamson

Computer Science

#1443

World Rank

#1492

Historical Rank

#711

USA Rank

Theoretical Computer Science

#103

World Rank

#103

Historical Rank

#27

USA Rank

computer-science Degrees

David P. Williamson

Mathematics

#2150

World Rank

#3362

Historical Rank

#859

USA Rank

Measure Theory

#1874

World Rank

#2286

Historical Rank

#577

USA Rank

mathematics Degrees

Download Badge

Computer Science
Mathematics

David P. Williamson's Degrees

PhD Computer Science University of California, Berkeley
Masters Computer Science University of California, Berkeley

Similar Degrees You Can Earn

Why Is David P. Williamson Influential?

(Suggest an Edit or Addition)

According to Wikipedia, David Paul Williamson is a professor of operations research at Cornell University, and the editor-in-chief of the SIAM Journal on Discrete Mathematics. He earned his Ph.D. in 1993 from the Massachusetts Institute of Technology under the supervision of Michel Goemans, and is best known for his work with Goemans on approximation algorithms based on semidefinite programming, for which they won the Fulkerson Prize in 2000. He also received the Frederick W. Lanchester Prize in 2013. In 2022 he received the AMS Steele Prize for Seminal Contribution to Research.

(See a Problem?)

David P. Williamson'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

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming (1995) (3632)
The Design of Approximation Algorithms (2011) (1110)
A general approximation technique for constrained forest problems (1992) (890)
.879-approximation algorithms for MAX CUT and MAX 2SAT (1994) (358)
The primal-dual method for approximation algorithms and its application to network design problems (1996) (331)
Scheduling parallel machines on-line (1991) (296)
Gadgets, approximation, and linear programming (1996) (284)
A note on the prize collecting traveling salesman problem (1993) (267)
Adversarial queuing theory (2001) (257)
New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem (1994) (248)
Improved approximation algorithms for network design problems (1994) (245)
The Approximability of Constraint Satisfaction Problems (2001) (212)
Short Shop Schedules (1997) (210)
A primal-dual approximation algorithm for generalized steiner network problems (1993) (209)
Improved approximation algorithms for capacitated facility location problems (1999) (208)
Adversarial queueing theory (1996) (188)
An adaptive algorithm for selecting profitable keywords for search-based advertising services (2006) (166)
Improved approximation algorithms for MAX SAT (2000) (155)
Searching the workplace web (2003) (153)
Analyzing the Held-Karp TSP Bound: A Monotonicity Property with Application (1990) (151)
Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming (2001) (150)
Deterministic pivoting algorithms for constrained ranking and clustering problems (2007) (124)
Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems (2006) (111)
A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs (1998) (103)
Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation (2001) (102)
Permutation vs. non-permutation flow shop schedules (1991) (98)
An efficient approximation algorithm for the survivable network design problem (1998) (84)
A general approach for incremental approximation and hierarchical clustering (2006) (82)
An approximation algorithm for minimum-cost vertex-connectivity problems (1997) (80)
Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems (2007) (78)
A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction (1997) (77)
The primal-dual method for approximation algorithms (2002) (74)
Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs (1998) (74)
A Faster, Better Approximation Algorithm for the Minimum Latency Problem (2008) (62)
Stackelberg thresholds in network routing games or the value of altruism (2007) (52)
Approximating the smallest k‐edge connected spanning subgraph by LP‐rounding (2005) (52)
Faster approximation algorithms for the minimum latency problem (2003) (51)
An iterative rounding 2-approximation algorithm for the element connectivity problem (2001) (48)
Approximation algorithms for prize collecting forest problems with submodular penalty functions (2007) (48)
Offline and online facility leasing (2008) (44)
ANALYSIS OF THE HELD-KARP HEURISTIC FOR THE TRAVELING SALESMAN PROBLEM (1990) (43)
Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time (2020) (43)
A primal-dual schema based approximation algorithm for the element connectivity problem (2002) (39)
Node-disjoint paths on the mesh and a new trade-off in VLSI layout (1996) (38)
On the Number of Small Cuts in a Graph (1996) (35)
Two-dimensional Gantt charts and a scheduling algorithm of Lawler (2000) (34)
Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems (1995) (33)
Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds (2017) (31)
Approximating minimum-cost graph problems with spanning tree edges (1994) (29)
A note on the generalized min-sum set cover problem (2011) (29)
On the design of approximation algorithms for a class of graph problems (1993) (28)
MAGNETIC RESONANCE IMAGING OF LASER POLARIZED LIQUID XENON (1999) (28)
A simple GAP-canceling algorithm for the generalized maximum flow problem (2006) (27)
A 1.47-approximation algorithm for a preemptive single-machine scheduling problem (2000) (26)
A simpler and better derandomization of an approximation algorithm for single source rent-or-buy (2007) (25)
Assortment optimization over time (2015) (22)
2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture (2014) (22)
Computational experience with an approximation algorithm on large-scale Euclidean matching instances (1994) (20)
The Reorientation of T-Cell Polarity and Inhibition of Immunological Synapse Formation by CD46 Involves Its Recruitment to Lipid Rafts (2011) (20)
A proof of the Boyd-Carr conjecture (2011) (19)
Approximating the smallest k-edge connected spanning subgraph by LP-rounding (2009) (18)
On-Line Scheduling of Parallel Machines (1990) (18)
An Experimental Evaluation of the Best-of-Many Christofides’ Algorithm for the Traveling Salesman Problem (2015) (17)
Primal-Dual Approximation Algorithms for Feedback Problems (1996) (16)
Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems (2020) (15)
Gadgets, Approximation, and Linear Programming (extended abstract). (1996) (15)
New 3⁄4 - Approximation Algorithms for MAX SAT (2001) (14)
An O(logn)-Competitive Algorithm for Online Constrained Forest Problems (2011) (14)
Pricing Problems Under the Nested Logit Model with a Quality Consistency Constraint (2017) (13)
Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching (2020) (13)
An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem (2016) (12)
Network Flow Algorithms (2019) (11)
Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements (2009) (11)
Prize-Collecting TSP with a Budget Constraint (2017) (11)
A new \frac34-approximation algorithm for MAX SAT (1993) (11)
On the integrality gap of the subtour LP for the 1,2-TSP (2011) (10)
Transcriptional down‐regulation of the rabbit pulmonary artery endothelin B receptor during phenotypic modulation (1999) (9)
The Online Connected Facility Location Problem (2014) (8)
Popular ranking (2014) (7)
Analysis of the Held-Karp lower bound for the asymmetric TSP (1992) (6)
Greedy algorithms for the single-demand facility location problem (2017) (6)
Lecture notes on approximation algorithms: Fall 1998 (1999) (6)
On Some Recent Approximation Algorithms for MAX SAT (2014) (5)
An Experimental Evaluation of Incremental and Hierarchical k-Median Algorithms (2011) (5)
The Online Prize-Collecting Facility Location Problem (2015) (5)
An Experimental Evaluation of the Best-of-Many Christofides’ Algorithm for the Traveling Salesman Problem (2017) (4)
Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem (2019) (4)
Online Constrained Forest and Prize-Collecting Network Design (2017) (4)
The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem (2017) (4)
An Experimental Evaluation of Semidefinite Programming and Spectral Algorithms for Max Cut (2022) (3)
Rank Aggregation: New Bounds for MCx (2015) (3)
A laser ablation resonance ionisation mass spectrometer (LA-RIMS) for the detection of isotope ratios of uranium at ultra-trace concentrations from solid particles and solutions (2019) (3)
A Randomized $$\mathrm {O}(\log n)$$O(logn)-Competitive Algorithm for the Online Connected Facility Location Problem (2016) (3)
On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems (2006) (3)
Solitary neurofibroma of the gallbladder. (1995) (3)
Approximation Algorithm for MAX-CUT (2007) (3)
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps (2019) (3)
The Optimization Complexity of Structure Maximization Problems (1996) (2)
A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction (1996) (2)
Integer Programming and Combinatorial Optimization, 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007, Proceedings (2007) (2)
Simple Approximation Algorithms for Balanced MAX 2SAT (2018) (2)
A Dual-Fitting $\frac{3}{2}$ -Approximation Algorithm for Some Minimum-Cost Graph Problems (2012) (2)
Orie 6334 Spectral Graph Theory (2016) (2)
Radiosynthesis and preliminary in vivo studies with [11C]SB216763: The first brain penetrative PET tracer for imaging of glycogen synthase kinase-3 (GSK-3) (2013) (2)
Routing and Job-shop Scheduling in O(congestion (1996) (2)
GILP: An Interactive Tool for Visualizing the Simplex Algorithm (2022) (1)
On the integrality gap of the subtour LP for the 1,2-TSP (2014) (1)
An Introduction to the Techniques (1)
Easy Capacitated Facility Location Problems, with Connections to Lot-Sizing (2020) (1)
Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm Flows (2021) (1)
Automated radiosynthesis and preclinical in vivo evaluation of [18F]Fluoroethylpuromycin as a potential radiotracer for imaging protein synthesis with PET. (2022) (1)
The Design of Approximation Algorithms: Rounding Data and Dynamic Programming (2011) (1)
Recursive Random Contraction Revisited (2020) (1)
Cosmetic Potential of a Recombinant 50 kDa Protein (2022) (1)
The Design of Approximation Algorithms: Further Uses of Random Sampling and Randomized Rounding of Linear Programs (2011) (1)
The Circlet Inequalities: A New, Circulant-Based Facet-Defining Inequality for the TSP (2020) (1)
The Two-Stripe Symmetric Circulant TSP is in P (2022) (1)
On Some Recent MAX SAT Approximation Algorithms (2013) (1)
Laser-polarized liquid xenon. (1998) (1)
Approximation Algorithms (1997) (1)
Orie 6334 Spectral Graph Theory Lecture 27 (2016) (1)
The Structure of Regulation (2021) (1)
The High Altitude Balloon Experiment demonstration of acquisition, tracking, and pointing technologies (HABE-ATP) (1995) (1)
A 3/2-approximation algorithm for some minimum-cost graph problems (2013) (1)
Maximizing a Submodular Function with Viability Constraints (2015) (1)
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems (2020) (1)
Bridging Continuous and Discrete Optimization November 6 , 2019 Lecture 16 (2019) (0)
Graph Coloring and Semidefinite Rank (2022) (0)
Eigenvector of the Largest Eigenvalue (2016) (0)
Semi-Lagrangian decentering and the growth of baroclinic instabilities (2003) (0)
The Design of Approximation Algorithms: Further Uses of Rounding Data and Dynamic Programming (2011) (0)
2 Algorithm for Graph Sparsification (2016) (0)
Simple Approximation Algorithms for Balanced MAX 2SAT (2016) (0)
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP (2022) (0)
Building Optimal Score Computation (1998) (0)
The Design of Approximation Algorithms: Greedy Algorithms and Local Search (2011) (0)
The Design of Approximation Algorithms: Random Sampling and Randomized Rounding of Linear Programs (2011) (0)
Proceedings of the 12th international conference on Integer Programming and Combinatorial Optimization (2007) (0)
Conditions of regulation (2021) (0)
Introduction to the structure of regulation (2021) (0)
Bridging Continuous and Discrete Optimization (2019) (0)
The Design of Approximation Algorithms: Deterministic Rounding of Linear Programs (2011) (0)
Maximizing a Submodular Function with Viability Constraints (2013) (0)
Special Issue: Integer Programming and Combinatorial Optimization (IPCO) 2021 (2022) (0)
A NOVEL RADIOLIGAND FOR ASSESSING BACE OCCUPANCY IN P-GP KO MOUSE BRAIN (2014) (0)
Orie 6334 Spectral Graph Theory 1 Low-stretch Trees 2 Algorithm for Unweighted Graphs (2016) (0)
The Design of Approximation Algorithms: Further Uses of Cuts and Metrics (2011) (0)
Online Constrained Forest and Prize-Collecting Network Design (2017) (0)
Frontmatter, Table of Contents, Preface, Organization, External Reviewers, List of Authors (2017) (0)
The Design of Approximation Algorithms: Further Uses of the Primal-Dual Method (2011) (0)
A NOVEL RADIOLIGAND FOR ASSESSING BACE OCCUPANCY IN P-GP KO MOUSE BRAIN (2014) (0)
A Combinatorial Cut-Based Algorithm for Solving Laplacian Linear Systems (2020) (0)
The Design of Approximation Algorithms: Bibliography (2011) (0)
Revisiting Garg's 2-Approximation Algorithm for the k-MST Problem in Graphs (2023) (0)
Tools from algorithms and complexity theory 1 (2009) (0)
A Short Primer on the Primal-Dual Method for Approximation Algorithms (Algorithm Engineering as a New Paradigm) (2001) (0)
The Design of Approximation Algorithms: Techniques in Proving the Hardness of Approximation (2011) (0)
The Matrix Multiplicative Weights Update Algorithm (2019) (0)
The Design of Approximation Algorithms: NP-Completeness (2011) (0)
MC4, Copeland and restart probabilities (2015) (0)
A revised view of regulation (2021) (0)
Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP (2019) (0)
The Design of Approximation Algorithms: Further Uses of Randomized Rounding of Semidefinite Programs (2011) (0)
Aprimal{dualinterpretationoftwo2-approximationalgorithms forthefeedbackvertexsetprobleminundirectedgraphs (1998) (0)
In vitro evaluation of GPR17 radioligands as potential CNS stem cell imaging agents (2021) (0)
MAX SATに対する新しい3/4-近似アルゴリズムとより高性能な近似アルゴリズム (1999) (0)
The Design of Approximation Algorithms: Cuts and Metrics (2011) (0)
A Final Assignment: (2019) (0)
A1.47-approximationalgorithmforapreemptivesingle-machine schedulingproblem (2000) (0)
Laboratorios Virtuales: Modelos para el aprendizaje virtual de automática industrial basados en LabVIEW (2015) (0)
The Design of Approximation Algorithms: Randomized Rounding of Semidefinite Programs (2011) (0)
Tight Bounds for Online Weighted Tree Augmentation (2019) (0)
A 3/2-approximation algorithm for some minimum-cost graph problems (2013) (0)
Erratum to “Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems” (2022) (0)
The Design of Approximation Algorithms: An Introduction to Approximation Algorithms (2011) (0)
The Design of Approximation Algorithms: Open Problems (2011) (0)
The Design of Approximation Algorithms: Further Uses of Greedy and Local Search Algorithms (2011) (0)
Expressive models in online learning (2010) (0)
Approximation Algorithms (cid:3) (2021) (0)
The Design of Approximation Algorithms: Linear Programming (2011) (0)
The Design of Approximation Algorithms: Preface (2011) (0)
Orie 633 Network Flows 1 Algorithms for Minimum-cost Circulations 1.1 a Cost-scaling Algorithm (2007) (0)
Gadgets, Approximation, and Linear Programming: Improved Hardness Results for Cut and Satisfiability Problems (Abstract of Invited Lecture) (1997) (0)
The Design of Approximation Algorithms: Further Uses of Deterministic Rounding of Linear Programs (2011) (0)
Development Of A Modular Performance-Portable Climate System Model (2001) (0)
Orie 6334 Spectral Graph Theory Lecture 27 Remix 1 Recap of Previous Lecture (2016) (0)
A Randomized O(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {O}(\log n)$$\end{document}-Competitive Al (2016) (0)
The Design of Approximation Algorithms: The Primal-Dual Method (2011) (0)
Scribe : Yingjie Bi 1 Approximate Potentials from Approximate Flow (2016) (0)
Enterprise and Desktop Search Lecture 2: Searching the Enterprise Web Searching the Enterprise Web Searching the Workplace Web (2009) (0)

This paper list is powered by the following services:

Other Resources About David P. Williamson

en.wikipedia.org

What Schools Are Affiliated With David P. Williamson?

David P. Williamson is affiliated with the following schools:

Image Attributions

Image Source for David P. Williamson