About

Anna Karlin is the Bill and Melinda Gates Chair in Computer Science and Engineering at the University of Washington. She received her Ph.D. from Stanford University in 1987. Prior to joining the University of Washington, she spent five years as a researcher at Digital Equipment Corporation's Systems Research Center. Her research primarily focuses on theoretical computer science, particularly the design and analysis of algorithms with an emphasis on probabilistic and online algorithms. Additionally, she works at the intersection of theory and other fields such as economics and game theory, data mining, operating systems, networks, and distributed systems.

Research topics

• Computer Science
• Mathematics
• Algorithm
• Mathematical optimization
• Statistics
• Combinatorics
• Mathematical economics
• Human–computer interaction
• Engineering
• Psychology

Selected publications

• Price Stability and Improved Buyer Utility with Presentation Design: A Theoretical Study of the Amazon Buy Box

  2025-04-22 · 1 citations

  articleOpen access

  Platforms design the form of presentation by which sellers are shown to the buyers. This design not only shapes the buyers' experience but also leads to different market equilibria or dynamics. One component in this design is through the platform's mediation of the search frictions experienced by the buyers for different sellers. We take a model of monopolistic competition and show that, on one hand, when all sellers have the same inspection costs, the market sees no stable price since the sellers always have incentives to undercut each other, and, on the other hand, the platform may stabilize the price by giving prominence to one seller chosen by a carefully designed mechanism. This calls to mind Amazon's Buy Box. We study natural mechanisms for choosing the prominent seller, characterize the range of equilibrium prices implementable by them, and find that in certain scenarios the buyers' surplus improves as the search friction increases.

  PublisherOA PDFDOI

• Non-Adaptive Matroid Prophet Inequalities

  Lecture notes in computer science · 2024-01-01 · 1 citations

  book-chapter
  PublisherDOI

• Maintaining Matroid Intersections Online

  Society for Industrial and Applied Mathematics eBooks · 2024-01-01 · 2 citations

  book-chapter

  Maintaining a maximum bipartite matching online while minimizing augmentations is a well studied problem, motivated by content delivery, job scheduling, and hashing. A breakthrough result of Bernstein, Holm, and Rotenberg (SODA 2018) resolved this problem up to a logarithmic factors. However, to model other problems in scheduling and resource allocation, we may need a richer class of combinatorial constraints (e.g., matroid constraints).

  PublisherDOI

• A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP

  Lecture notes in computer science · 2023-01-01 · 9 citations

  book-chapter1st author
  PublisherDOI

• Maintaining Matroid Intersections Online

  arXiv (Cornell University) · 2023-09-18

  preprintOpen access

  Maintaining a maximum bipartite matching online while minimizing recourse/augmentations is a well studied problem, motivated by content delivery, job scheduling, and hashing. A breakthrough result of Bernstein, Holm, and Rotenberg (\emph{SODA 2018}) resolved this problem up to a logarithmic factors. However, we may need a richer class of combinatorial constraints (e.g., matroid constraints) to model other problems in scheduling and resource allocation. We consider the problem of maintaining a maximum independent set of an arbitrary matroid $\mathcal{M}$ and a partition matroid $\mathcal{P}$ in the online setting. Specifically, at each timestep $t$ one part $P_t$ of the partition matroid (i.e., a subset of elements) is revealed: we must now select at most one of these newly-revealed elements, but can exchange some of the previously selected elements for new ones from previous parts, to maintain a maximum independent set on the elements seen thus far. The goal is to minimize the number of augmentations/changes done by our algorithm. If $\mathcal{M}$ is also a partition matroid, we recover the problem of maintaining a maximum bipartite matching online with recourse as a special case. In our work, we allow arbitrary matroids $\mathcal{M}$, and so we can model broader classes of problems. Our main result is an $O(n \log^2 n)$-competitive algorithm, where $n$ is the rank of the largest common base; this matches the current best quantitative bound for the bipartite matching special case. Our result builds substantively on the breakthrough result of Bernstein, Holm, and Rotenberg for maintaining bipartite matchings: a key contribution of our work is to make connections to market equilibria and prices, and our use of properties of these equilibria in submodular utility allocation markets to prove our bound on the number of augmentations.

  PublisherOA PDFDOI

• Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue

  Mathematics of Operations Research · 2023-05-15 · 4 citations

  articleSenior author

  We study combinatorial auctions with interdependent valuations, where each agent i has a private signal s i that captures her private information and the valuation function of every agent depends on the entire signal profile, [Formula: see text]. The literature in economics shows that the interdependent model gives rise to strong impossibility results and identifies assumptions under which optimal solutions can be attained. The computer science literature provides approximation results for simple single-parameter settings (mostly single-item auctions or matroid feasibility constraints). Both bodies of literature focus largely on valuations satisfying a technical condition termed single crossing (or variants thereof). We consider the class of submodular over signals (SOS) valuations (without imposing any single crossing-type assumption) and provide the first welfare approximation guarantees for multidimensional combinatorial auctions achieved by universally ex post incentive-compatible, individually rational mechanisms. Our main results are (i) four approximation for any single-parameter downward-closed setting with single-dimensional signals and SOS valuations; (ii) four approximation for any combinatorial auction with multidimensional signals and separable-SOS valuations; and (iii) (k + 3) and (2 log(k) + 4) approximation for any combinatorial auction with single-dimensional signals, with k-sized signal space, for SOS and strong-SOS valuations, respectively. All of our results extend to a parameterized version of SOS, d-approximate SOS, while losing a factor that depends on d. Funding: A. Eden was partially supported by NSF Award IIS-2007887, the European Research Council (ERC) under the European Union's Seventh Framework Programme [FP7/2007-2013]/ERC Grant Agreement 337122, by the Israel Science Foundation [Grant 317/17], and by an Amazon research award. M. Feldman received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program [Grant Agreement 866132], by the Israel Science Foundation [Grant 317/17], by an Amazon research award, and by the NSF-BSF [Grant 2020788]. The work of K. Goldner was supported partially by NSF awards DMS-1903037 and CNS-2228610 and a Shibulal Family Career Development Professorship. A. R. Karlin was supported by the NSF-CCF [Grant 1813135].

  PublisherDOI

• A (Slightly) Improved Approximation Algorithm for Metric TSP

  Operations Research · 2023 · 31 citations

  1st authorCorresponding
  • Mathematics
  • Combinatorics
  • Algorithm

  In “An Improved Approximation Algorithm for TSP,” Karlin, Klein, and Oveis Gharan design the first improvement over the classical 1.5 approximation algorithm of Christofides-Serdyukov after more than 40 years. Their algorithm first chooses a random spanning tree from the maximum entropy distribution of spanning trees with marginals equal to the optimum LP solution of TSP, and then, similar to Christofides’ algorithm, it adds the minimum cost matching on the odd degree vertices of the tree. To analyze their simple algorithms, they prove and exploit new tools from the theory of strongly Rayleigh distributions.

  PublisherDOI

• Simple pricing schemes for consumers with evolving values

  Games and Economic Behavior · 2022-04-01 · 2 citations

  article
  PublisherDOI

• A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP

  2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) · 2022-10-01 · 12 citations

  article1st authorCorresponding

  In this extended abstract, we show that for some $\epsilon>10^{-36}$ and any metric TSP instance, the max entropy algorithm studied by [1] returns a solution of expected cost at most $\frac{3}{2}-\epsilon$ times the cost of the optimal solution to the subtour elimination LP. This implies that the integrality gap of the subtour LP is at most $\frac{3}{2}-\epsilon$. This analysis also shows that there is a randomized $\frac{3}{2}-\epsilon$ approximation for the 2-edge-connected multi-subgraph problem, improving upon Christofides’ algorithm.

  PublisherDOI

• A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP

  arXiv (Cornell University) · 2022-12-13

  preprintOpen access1st authorCorresponding

  We show that the max entropy algorithm can be derandomized (with respect to a particular objective function) to give a deterministic $3/2-ε$ approximation algorithm for metric TSP for some $ε> 10^{-36}$. To obtain our result, we apply the method of conditional expectation to an objective function constructed in prior work which was used to certify that the expected cost of the algorithm is at most $3/2-ε$ times the cost of an optimal solution to the subtour elimination LP. The proof in this work involves showing that the expected value of this objective function can be computed in polynomial time (at all stages of the algorithm's execution).

  PublisherOA PDFDOI

Recent grants

• AF: Small: Towards More Realistic Models in Algorithmic Mechanism Design

  NSF · $450k · 2014–2018

• Mechanism Design for Profit Maximization

  NSF · $330k · 2006–2010

• AF: SMALL : Algorithmic and Game Theoretic Problems Arising in Modern Matching Markets

  NSF · $400k · 2018–2022

• AF: Small: Beyond Worst-Case Analysis in Approximation Algorithms, Algorithmic Mechanism Design and Online Algorithms

  NSF · $500k · 2010–2014

Frequent coauthors

• Shayan Oveis Gharan

  23 shared

• Nathan Klein

  Institute for Advanced Study

  20 shared

• Yuval Peres

  Beijing Institute of Mathematical Sciences and Applications

  19 shared

• Amos Fiat

  17 shared

• Jason D. Hartline

  Northwestern University

  15 shared

• Yossi Azar

  13 shared

• Claire Mathieu

  Institut de Recherche en Informatique Fondamentale

  13 shared

• Henry M. Levy

  Google (United States)

  13 shared

Labs

• Anna Karlin's LabPI

  The lab focuses on the design and analysis of algorithms, particularly probabilistic and online algorithms, and works at the interface between theory and other areas such as economics and game theory, data mining, operating systems, networks, and distributed systems.

Education

• Ph.D.

  Stanford University

  1987

Awards & honors

• Bill & Melinda Gates Chair in Computer Science & Engineering