Arrow Research search

Author name cluster

Anna R. Karlin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

38 papers
2 author rows

Possible papers

38

FOCS Conference 2022 Conference Paper

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

  • Anna R. Karlin
  • Nathan Klein
  • Shayan Oveis Gharan

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.

Details

STOC Conference 2020 Conference Paper

An improved approximation algorithm for TSP in the half integral case

  • Anna R. Karlin
  • Nathan Klein
  • Shayan Oveis Gharan

We design a 1.49993-approximation algorithm for the metric traveling salesperson problem (TSP) for instances in which an optimal solution to the subtour linear programming relaxation is half-integral. These instances received significant attention over the last decade due to a conjecture of Schalekamp, Williamson and van Zuylen stating that half-integral LP solutions have the largest integrality gap over all fractional solutions. So, if the conjecture of Schalekamp et al. holds true, our result shows that the integrality gap of the subtour polytope is bounded away from 3/2.

Details

STOC Conference 2018 Conference Paper

A simply exponential upper bound on the maximum number of stable matchings

  • Anna R. Karlin
  • Shayan Oveis Gharan
  • Robbie Weber

Stable matching is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale and Shapley. In this paper, we provide a new upper bound on f ( n ), the maximum number of stable matchings that a stable matching instance with n men and n women can have. It has been a long-standing open problem to understand the asymptotic behavior of f ( n ) as n →∞, first posed by Donald Knuth in the 1970s. Until now the best lower bound was approximately 2.28 n , and the best upper bound was 2 n log n − O ( n ) . In this paper, we show that for all n , f ( n ) ≤ c n for some universal constant c . This matches the lower bound up to the base of the exponent. Our proof is based on a reduction to counting the number of downsets of a family of posets that we call “mixing”. The latter might be of independent interest.

Details

STOC Conference 2017 Conference Paper

Stability of service under time-of-use pricing

  • Shuchi Chawla 0001
  • Nikhil R. Devanur
  • Alexander E. Holroyd
  • Anna R. Karlin
  • James B. Martin
  • Balasubramanian Sivan

We consider time-of-use pricing as a technique for matching supply and demand of temporal resources with the goal of maximizing social welfare. Relevant examples include energy, computing resources on a cloud computing platform, and charging stations for electric vehicles, among many others. A client/job in this setting has a window of time during which he needs service, and a particular value for obtaining it. We assume a stochastic model for demand, where each job materializes with some probability via an independent Bernoulli trial. Given a per-time-unit pricing of resources, any realized job will first try to get served by the cheapest available resource in its window and, failing that, will try to find service at the next cheapest available resource, and so on. Thus, the natural stochastic fluctuations in demand have the potential to lead to cascading overload events. Our main result shows that setting prices so as to optimally handle the expected demand works well: with high probability, when the actual demand is instantiated, the system is stable and the expected value of the jobs served is very close to that of the optimal offline algorithm.

Details

SODA Conference 2016 Conference Paper

Simple Pricing Schemes For Consumers With Evolving Values

  • Shuchi Chawla 0001
  • Nikhil R. Devanur
  • Anna R. Karlin
  • Balasubramanian Sivan

We consider a pricing problem where a buyer is interested in purchasing/using a good, such as an app or music or software, repeatedly over time. The consumer discovers his value for the good only as he uses it, and the value evolves with each use. Optimizing for the seller's revenue in such dynamic settings is a complex problem and requires assumptions about how the buyer behaves before learning his future value(s), and in particular, how he reacts to risk. We explore the performance of a class of pricing mechanisms that are extremely simple for both the buyer and the seller to use: the buyer reacts to prices myopically without worrying about how his value evolves in the future; the seller needs to optimize for revenue over a space of only two parameters, and can do so without knowing the buyer's risk profile or fine details of the value evolution process. We present simple-versus-optimal type results, namely that under certain assumptions, simple pricing mechanisms of the above form are approximately optimal regardless of the buyer's risk profile. Our results assume that the buyer's value per usage evolves as a martingale. For our main result, we consider pricing mechanisms in which the seller offers the product for free for a certain number of uses, and then charges an appropriate fixed price per usage. We assume that the buyer responds by buying the product for as long as his value exceeds the fixed price. Importantly, the buyer does not need to know anything about how his future value will evolve, only how much he wants to use the product right now. Regardless of the buyers' initial value, our pricing captures as revenue a constant fraction of the total value that the buyers accumulate in expectation over time.

Details

FOCS Conference 2007 Conference Paper

Balloon Popping With Applications to Ascending Auctions

  • Nicole Immorlica
  • Anna R. Karlin
  • Mohammad Mahdian
  • Kunal Talwar

We study the power of ascending auctions in a scenario in which a seller is selling a collection of identical items to anonymous unit'demand bidders. We show that even with full knowledge of the set of bidders' private valuations for the items, if the bidders are ex-ante identical, no ascending auction can extract more than a constant. times the revenue of the best fixed-price scheme. This problem is equivalent to the problem of coming up with an optimal strategy for blowing up indistinguishable balloons with known capacities in order to maximize the amount of contained, air. We show that the algorithm which simply inflates all balloons to a fixed volume is close to optimal in this setting.

Details

FOCS Conference 2005 Conference Paper

Beyond VCG: Frugality of Truthful Mechanisms

  • Anna R. Karlin
  • David Kempe 0001
  • Tami Tamir

We study truthful mechanisms for auctions in which the auctioneer is trying to hire a team of agents to perform a complex task, and paying them for their work. As common in the field of mechanism design, we assume that the agents are selfish and will act in such a way as to maximize their profit, which in particular may include misrepresenting their true incurred cost. Our first contribution is a new and natural definition of the frugality ratio of a mechanism, measuring the amount by which a mechanism "overpays ", and extending previous definitions to all monopoly-free set systems. After reexamining several known results in light of this new definition, we proceed to study in detail shortest path auctions and 'r-out-of-k sets" auctions. We show that when individual set systems (e. g. , graphs) are considered instead of worst cases over all instances, these problems exhibit a rich structure, and the performance of mechanisms may be vastly different. In particular, we show that the well-known VCG mechanism may be far from optimal in these settings, and we propose and analyze a mechanism that is always within a constant factor of optimal.

Details

STOC Conference 2002 Conference Paper

Competitive generalized auctions

  • Amos Fiat
  • Andrew V. Goldberg
  • Jason D. Hartline
  • Anna R. Karlin

We describe mechanisms for auctions that are simultaneously truthful (alternately known as strategy-proof or incentive compatible) and guarantee high "net" profit. We make use of appropriate variants of competitive analysis of algorithms in designing and analyzing our mechanisms. Thus, we do not require any probabilistic assumptions on bids.We present two new concepts regarding auctions, that of a cancellable auction and that of a generalized auction. We use cancellable auctions in the design of generalized auctions, but they are of independent interest as well. Cancellable auctions have the property that if the revenue collected does not meet certain predetermined criteria, then the auction can be cancelled and the resulting auction is still truthful. The trivial approach (run a truthful auction and cancel if needed) yields an auction that is not necessarily truthfu.Generalized auctions can be used to model many problems previously considered in the literature, as well as numerous new problems. In particular, we give the first truthful profit-maximizing auctions for problems such as conditional financing and multicast.

Details

TCS Journal 2002 Journal Article

On list update and work function algorithms

  • Eric J. Anderson
  • Kirsten Hildrum
  • Anna R. Karlin
  • April Rasala
  • Michael Saks

The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system algorithm, called the work function algorithm, has constant competitive ratio for list update. In the process, we present a new formulation of the well-known “list factoring” technique in terms of a partial order on the elements of the list. This approach leads to a new simple proof that a large class of online algorithms, including Move-To-Front, is (2−1/k)-competitive, for k the list length.

Details DOI

STOC Conference 2001 Conference Paper

Dynamic TCP acknowledgement and other stories about e/(e-1)

  • Anna R. Karlin
  • Claire Mathieu
  • Dana Randall

We present the first optimal randomized online algorithms for the TCP acknowledgment problem [5] and the Bahncard problem [7]. These problems are well-known to be generalizations of the classical online ski rental problem, however, they appeared to be harder. In this paper, we demonstrate that a number of online algorithms which have optimal competitive ratios of e /( e -1), including these, are fundamentally no more complex than ski rental. Our results also suggest a clear paradigm for solving ski rental-like problems.

Details

STOC Conference 2001 Conference Paper

Spectral analysis of data

  • Yossi Azar
  • Amos Fiat
  • Anna R. Karlin
  • Frank McSherry
  • Jared Saia

Experimental evidence suggests that spectral techniques are valuable for a wide range of applications. A partial list of such applications include (i) semantic analysis of documents used to cluster documents into areas of interest, (ii) collaborative filtering --- the reconstruction of missing data items, and (iii) determining the relative importance of documents based on citation/link structure. Intuitive arguments can explain some of the phenomena that has been observed but little theoretical study has been done. In this paper we present a model for framing data mining tasks and a unified approach to solving the resulting data mining problems using spectral analysis. These results give strong justification to the use of spectral techniques for latent semantic indexing, collaborative filtering, and web site ranking.

Details

FOCS Conference 2001 Conference Paper

Web Search via Hub Synthesis

  • Dimitris Achlioptas
  • Amos Fiat
  • Anna R. Karlin
  • Frank McSherry

We present a model for web search that captures in a unified manner three critical components of the problem: how the link structure of the web is generated, how the content of a web document is generated, and how a human searcher generates a query. The key to this unification lies in capturing the correlations between these components in terms of proximity in a shared latent semantic space. Given such a combined model, the correct answer to a search query is well defined, and thus it becomes possible to evaluate web search algorithms rigorously. We present a new web search algorithm, based on spectral techniques, and prove that it is guaranteed to produce an approximately correct answer in our model. The algorithm assumes no knowledge of the model, and is well-defined regardless of the model's accuracy.

Details

FOCS Conference 1996 Conference Paper

Near-Optimal Parallel Prefetching and Caching

  • Tracy Kimbrel
  • Anna R. Karlin

The authors consider algorithms for integrated prefetching and caching in a model with a fixed-size cache and any number of backing storage devices (disks). Previously, the single disk case was considered by Cao et al. (1995). They show that the natural extension of their aggressive algorithm to the parallel disk case is suboptimal by a factor near the number of disks in the worst case. The main result is a new algorithm, reverse aggressive, with near-optimal performance in the presence of multiple disks.

Details

TCS Journal 1994 Journal Article

On-line load balancing

  • Yossi Azar
  • Andrei Z. Broder
  • Anna R. Karlin

The setup for our problem consists of n servers that must complete a set of tasks. Each task can be handled only by a subset of the servers, requires a different level of service, and once assigned cannot be reassigned. We make the natural assumption that the level of service is known at arrival time, but that the duration of service is not. The on-line load balancing problem is to assign each task to an appropriate server in such a way that the maximum load on the servers is minimized. In this paper we derive matching upper and lower bounds for the competitive ratio of the on-line greedy algorithm for this problem, namely, [(3n) 2 3 /2](1+o(1)), and derive a lower bound, Ω(n 1 2 ), for any other deterministic or randomized on-line algorithm.

Details DOI

STOC Conference 1992 Conference Paper

Biased Random Walks

  • Yossi Azar
  • Andrei Z. Broder
  • Anna R. Karlin
  • Nati Linial
  • Steven J. Phillips

How much can an imperfect source of randomness affect an algorithm? We examine several simple questions of this type concerning the long-term behavior of a random walk on a finite graph. In our setup, each step of the random walk a “controller” can, with a certain small probability, fix the next step, thus introducing a bias. We analyze the extent to which the bias can affect the limit behavior of the walk. The controller is assumed to associate a real, nonnegative, “benefit” with each state, and to strive to maximize the long-term expected benefit. We derive tight bounds on the maximum of this objective function over all controller's strategies, and present polynomial time algorithms for computing the optimal controller strategy.

Details

FOCS Conference 1992 Conference Paper

Markov Paging (Extended Abstract)

  • Anna R. Karlin
  • Steven J. Phillips
  • Prabhakar Raghavan

This paper considers the problem of paging under the assumption that the sequence of pages accessed is generated by a Markov chain. The authors use this model to study the fault-rate of paging algorithms, a quantity of interest to practitioners. They first draw on the theory of Markov decision processes to characterize the paging algorithm that achieves optimal fault-rate on any Markov chain. They address the problem of efficiently devising a paging strategy with low fault-rate for a given Markov chain. They show that a number of intuitively good approaches fail. Their main result is an efficient procedure that, on any Markov chain, will give a paging algorithm with fault-rate at most a constant times optimal. Their techniques also show that some algorithms that do poorly in practice fail in the Markov setting, despite known (good) performance guarantees when the requests are generated independently from a probability distribution. >

Details

FOCS Conference 1992 Conference Paper

On-line Load Balancing (Extended Abstract)

  • Yossi Azar
  • Andrei Z. Broder
  • Anna R. Karlin

The setup for the authors' problem consists of n servers that must complete a set of tasks. Each task can be handled only by a subset of the servers, requires a different level of service, and once assigned can not be re-assigned. They make the natural assumption that the level of service is known at arrival time, but that the duration of service is not. The on-line load balancing problem is to assign each task to an appropriate server in such a way that the maximum load on the servers is minimized. The authors derive matching upper and lower bounds for the competitive ratio of the on-line greedy algorithm for this problem, namely /sup (3n)2/3///sub 2/(1+o(1)), and derive a lower bound, Omega ( square root n), for any other deterministic or randomized on-line algorithm. >

Details

FOCS Conference 1990 Conference Paper

Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors (Extended Abstract)

  • Christos Kaklamanis
  • Anna R. Karlin
  • Frank Thomson Leighton
  • Victor Milenkovic
  • Prabhakar Raghavan
  • Satish Rao
  • Clark D. Thompson
  • A. Tsantilas

The computational power of 2-D and 3-D processor arrays that contain a potentially large number of faults is analyzed. Both a random and a worst-case fault model are considered, and it is proved that in either scenario low-dimensional arrays are surprisingly fault tolerant. It is also shown how to route, sort, and perform systolic algorithms for problems such as matrix multiplication in optimal time on faulty arrays. In many cases, the running time is the same as if there were no faults in the array (up to constant factors). On the negative side, it is shown that any constant congestion embedding of an n*n fault-free array on an n*n array with Theta (n/sup 2/) random faults (or Theta (log n) worst-case faults) requires dilation Theta (log n). For 3-D arrays, knot theory is used to prove that the required dilation is Omega ( square root log n). >

Details

STOC Conference 1989 Conference Paper

Trading Space for Time in Undirected s-t Connectivity

  • Andrei Z. Broder
  • Anna R. Karlin
  • Prabhakar Raghavan
  • Eli Upfal

Aleliunas et al. [1] posed the following question: “The reachability problem for undirected graphs can be solved in logspace and O ( mn ) time [ m is the number of edges and n is the number of vertices] by a probabilistic algorithm that simulates a random walk, or in linear time and space by a conventional deterministic graph traversal algorithm. Is there a spectrum of time-space trade-offs between these extremes?” We answer this question in the affirmative for linear-sized graphs by presenting an algorithm which is faster than the random walk by a factor essentially proportional to the size of its workspace. For denser graphs, the algorithm is faster than the random walk but the speed-up factor is smaller.

Details

FOCS Conference 1988 Conference Paper

Bounds on the Cover Time (Preliminary Version)

  • Andrei Z. Broder
  • Anna R. Karlin

A particle that moves on a connected unidirected graph G with n vertices is considered. At each step the particle goes from the current vertex to one of its neighbors, chosen uniformly at random. The cover time is the first time when the particle has visited all the vertices in the graph, starting from a given vertex. Upper and lower bounds are presented that relate the expected cover time for a graph to the eigenvalues of the Markov chain that describes the above random walk. An interesting consequence is that regular expander graphs have expected cover time theta (n log n). >

Details

FOCS Conference 1988 Conference Paper

Dynamic Perfect Hashing: Upper and Lower Bounds

  • Martin Dietzfelbinger
  • Anna R. Karlin
  • Kurt Mehlhorn
  • Friedhelm Meyer auf der Heide
  • Hans Rohnert
  • Robert Endre Tarjan

A randomized algorithm is given for the dictionary problem with O(1) worst-case time for lookup and O(1) amortized expected time for insertion and deletion. An Omega (log n) lower bound is proved for the amortized worst-case time complexity of any deterministic algorithm in a class of algorithms encompassing realistic hashing-based schemes. If the worst-case lookup time is restricted to k, then the lower bound for insertion becomes Omega (kn/sup 1/k/). >

Details

FOCS Conference 1986 Conference Paper

Competitive Snoopy Caching

  • Anna R. Karlin
  • Mark S. Manasse
  • Larry Rudolph
  • Daniel Dominic Sleator

In a snoopy cache multiprocessor system, each processor has a cache in which it stores blocks of data. Each cache is connected to a bus used to communicate with the other caches and with main memory. For several of the proposed models of snoopy caching, we present new on-line algorithms which decide, for each cache, which blocks to retain and which to drop in order to minimize communication over the bus. We prove that, for any sequence of operations, our algorithms' communication costs are within a constant factor of the minimum required for that sequence; for some of our algorithms we prove that no on-line algorithm has this property with a smaller constant.

Details
v2026.09.13