Anna R. Karlin

Proceedings of the Integer Programming and Combinatorial Optimization, 2023

Matroid Partition Property and the Secretary Problem.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Simple pricing schemes for consumers with evolving values.

[BibT_eX]

[DOI]

Shuchi Chawla

Nikhil R. Devanur

Balasubramanian Sivan

Games Econ. Behav., 2022

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

[BibT_eX]

[DOI]

CoRR, 2022

An improved approximation algorithm for the minimum <i>k</i>-edge connected multi-subgraph problem.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

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

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem.

[BibT_eX]

[DOI]

CoRR, 2021

A (slightly) improved approximation algorithm for metric TSP.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2020

Non-Adaptive Matroid Prophet Inequalities.

[BibT_eX]

[DOI]

CoRR, 2020

Competition Alleviates Present Bias in Task Completion.

[BibT_eX]

[DOI]

Aditya Saraf

Jamie Morgenstern

Proceedings of the Web and Internet Economics - 16th International Conference, 2020

An improved approximation algorithm for TSP in the half integral case.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Beyond Competitive Analysis.

[BibT_eX]

[DOI]

Elias Koutsoupias

Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020

2019

Energy Equilibria in Proof-of-Work Mining.

[BibT_eX]

[DOI]

Amos Fiat

Christos H. Papadimitriou

Elias Koutsoupias

Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue.

[BibT_eX]

[DOI]

Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

2018

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

[BibT_eX]

[DOI]

Robbie Weber

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017

Stability of service under time-of-use pricing.

[BibT_eX]

[DOI]

Balasubramanian Sivan

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

A Prior-Independent Revenue-Maximizing Auction for Multiple Additive Bidders.

[BibT_eX]

[DOI]

Kira Goldner

Proceedings of the Web and Internet Economics - 12th International Conference, 2016

The FedEx Problem.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Conference on Economics and Computation, 2016

Carpooling in Social Networks.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

On a Competitive Secretary Problem.

[BibT_eX]

[DOI]

Eric Lei

Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

2014

Convergence of Position Auctions under Myopic Best-Response Dynamics.

[BibT_eX]

[DOI]

ACM Trans. Economics and Comput., 2014

How to sell an app: pay-per-play or buy-it-now?

[BibT_eX]

[DOI]

Shuchi Chawla

Nikhil R. Devanur

Balasubramanian Sivan

CoRR, 2014

Approximate revenue maximization in interdependent value settings.

[BibT_eX]

[DOI]

Shuchi Chawla

Hu Fu

Proceedings of the ACM Conference on Economics and Computation, 2014

2013

Selling in Exclusive Markets: Some Observations on Prior-Free Mechanism Design.

[BibT_eX]

[DOI]

C. Thach Nguyen

Yuval Peres

ACM Trans. Economics and Comput., 2013

Approaching utopia: strong truthfulness and externality-resistant mechanisms.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2013

On Revenue Maximization for Agents with Costly Information Acquisition - Extended Abstract.

[BibT_eX]

[DOI]

L. Elisa Celis

Dimitrios C. Gklezakos

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Using behavioral data to identify interviewer fabrication in surveys.

[BibT_eX]

[DOI]

Proceedings of the 2013 ACM SIGCHI Conference on Human Factors in Computing Systems, 2013

2012

Evaluating Competitive Game Balance with Restricted Play.

[BibT_eX]

[DOI]

Proceedings of the Eighth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 2012

Approximately Revenue-Maximizing Auctions for Deliberative Agents.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012

2011

Prior-Independent Multi-parameter Mechanism Design.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics - 7th International Workshop, 2011

Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack.

[BibT_eX]

[DOI]

Claire Mathieu

C. Thach Nguyen

Proceedings of the Integer Programming and Combinatoral Optimization, 2011

2010

Algorithms for Data Migration.

[BibT_eX]

[DOI]

Algorithmica, 2010

2009

Approximating Matches Made in Heaven.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

On Revenue Maximization in Second-Price Ad Auctions.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2009

2008

Thinking Twice about Second-Price Ad Auctions

[BibT_eX]

[DOI]

CoRR, 2008

On the Equilibria and Efficiency of the GSP Mechanism in Keyword Auctions with Externalities.

[BibT_eX]

[DOI]

Ioannis Giotis

Proceedings of the Internet and Network Economics, 4th International Workshop, 2008

Auctions for structured procurement.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Improved Approximation Algorithms for Budgeted Allocations.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007

Cheap labor can be expensive.

[BibT_eX]

[DOI]

Ning Chen

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Greedy bidding strategies for keyword auctions.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

Balloon Popping With Applications to Ascending Auctions.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Ad Auctions - Current and Future Research.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects in Information and Management, 2007

2006

Competitive auctions.

[BibT_eX]

[DOI]

Games Econ. Behav., 2006

2005

On profit-maximizing envy-free pricing.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Beyond VCG: Frugality of Truthful Mechanisms.

[BibT_eX]

[DOI]

David Kempe

Tami Tamir

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

A Lower Bound on the Competitive Ratio of Truthful Auctions.

[BibT_eX]

[DOI]

Proceedings of the STACS 2004, 2004

2003

Dynamic TCP Acknowledgment and Other Stories about e/(e-1).

[BibT_eX]

Claire Kenyon

Dana Randall

Algorithmica, 2003

2002

On list update and work function algorithms.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

A quantitative evaluation of traffic-aware routing strategies.

[BibT_eX]

[DOI]

Comput. Commun. Rev., 2002

Competitive generalized auctions.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Dynamically Fault-Tolerant Content Addressable Networks.

[BibT_eX]

[DOI]

Proceedings of the Peer-to-Peer Systems, First International Workshop, 2002

Mechanism Design for Fun and Profit.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2002

Truthful and Competitive Double Auctions.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2002

2001

Network support for IP traceback.

[BibT_eX]

[DOI]

IEEE/ACM Trans. Netw., 2001

An Experimental Study of Data Migration Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Engineering, 2001

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

[BibT_eX]

[DOI]

Claire Kenyon

Dana Randall

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Spectral analysis of data.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

On algorithms for efficient data migration.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Web Search via Hub Synthesis.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2001

Web Search via Hub Synthesis.

[BibT_eX]

[DOI]

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Spectral Analysis for Data Mining.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Engineering and Experimentation, Third International Workshop, 2001

2000

Near-Optimal Parallel Prefetching and Caching.

[BibT_eX]

[DOI]

Tracy Kimbrel

SIAM J. Comput., 2000

Markov Paging.

[BibT_eX]

[DOI]

Steven J. Phillips

Prabhakar Raghavan

SIAM J. Comput., 2000

Random walks with "back buttons" (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Practical network support for IP traceback.

[BibT_eX]

[DOI]

Proceedings of the ACM SIGCOMM 2000 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, August 28, 2000

1999

Balanced Allocations.

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

A Note on the Influence of an epsilon-Biased Random Source.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1999

Organization-Based Analysis of Web-Object Sharing and Caching.

[BibT_eX]

[DOI]

Proceedings of the 2nd USENIX Symposium on Internet Technologies and Systems, 1999

On the scale and performance of cooperative Web proxy caching.

[BibT_eX]

[DOI]

Proceedings of the 17th ACM Symposium on Operating System Principles, 1999

Potentials and Limitations of Fault-Based Markov Prefetching for Virtual Memory Pages.

[BibT_eX]

[DOI]

Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, 1999

Pursuing the Performance Potential of Dynamic Cache Line Sizes.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Conference On Computer Design, 1999

1998

Implementing Cooperative Prefetching and Caching in a Globally-Managed Memory System.

[BibT_eX]

[DOI]

Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, 1998

1996

Implementation and Performance of Integrated Application-Controlled File Caching, Prefetching, and Disk Scheduling.

[BibT_eX]

[DOI]

ACM Trans. Comput. Syst., 1996

Strongly Competitive Algorithms for Paging with Locality of Reference.

[BibT_eX]

[DOI]

Sandy Irani

Steven J. Phillips

SIAM J. Comput., 1996

Biased Random Walks.

[BibT_eX]

[DOI]

Comb., 1996

Integrating Parallel Prefetching and Caching.

[BibT_eX]

[DOI]

Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, 1996

A Trace-Driven Comparison of Algorithms for Parallel Prefetching and Caching.

[BibT_eX]

[DOI]

Proceedings of the Second USENIX Symposium on Operating Systems Design and Implementation (OSDI), 1996

Two Adaptive Hybrid Cache Coherency Protocols.

[BibT_eX]

[DOI]

Craig Anderson

Proceedings of the Second International Symposium on High-Performance Computer Architecture, 1996

On the Performance of Competitive Algorithms in Practice.

[BibT_eX]

[DOI]

Proceedings of the Online Algorithms, 1996

Reducing Network Latency Using Subpages in a Global Memory Environment.

[BibT_eX]

[DOI]

Proceedings of the ASPLOS-VII Proceedings, 1996

1995

Randomized and multipointer paging with locality of reference.

[BibT_eX]

[DOI]

Amos Fiat

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Implementing Global Memory Management in a Workstation Cluster.

[BibT_eX]

[DOI]

Chandramohan A. Thekkath

Proceedings of the Fifteenth ACM Symposium on Operating System Principles, 1995

A Study of Integrated Prefetching and Caching Strategies.

[BibT_eX]

[DOI]

Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, 1995

Reducing TLB and Memory Overhead Using Online Superpage Promotion.

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual International Symposium on Computer Architecture, 1995

1994

On-Line Load Balancing.

[BibT_eX]

[DOI]

Yossi Azar

Theor. Comput. Sci., 1994

Dynamic Perfect Hashing: Upper and Lower Bounds.

[BibT_eX]

[DOI]

Martin Dietzfelbinger

Friedhelm Meyer auf der Heide

Kurt Mehlhorn

Hans Rohnert

Robert Endre Tarjan

SIAM J. Comput., 1994

Trading Space for Time in Undirected s-t Connectivity.

[BibT_eX]

[DOI]

SIAM J. Comput., 1994

Chiron parallel program performance visualization system.

[BibT_eX]

[DOI]

Comput. Aided Des., 1994

Competitive Randomized Algorithms for Nonuniform Problems.

[BibT_eX]

[DOI]

Algorithmica, 1994

On the fault tolerance of the butterfly.

[BibT_eX]

[DOI]

Greg Nelson

Hisao Tamaki

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Balanced allocations (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

1992

Factors in the Performance of the AN1 Computer Network.

[BibT_eX]

[DOI]

Susan S. Owicki

Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, 1992

Markov Paging (Extended Abstract)

[BibT_eX]

[DOI]

Steven J. Phillips

Prabhakar Raghavan

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

On-line Load Balancing (Extended Abstract)

[BibT_eX]

[DOI]

Yossi Azar

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991

Empirical Studies of Competitive Spinning for a Shared-Memory Multiprocessor.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth ACM Symposium on Operating System Principles, 1991

On the Parallel Complexity of Evaluating Game Trees.

[BibT_eX]

[DOI]

Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

1990

Competitive Randomized Algorithms for Non-Uniform Problems.

[BibT_eX]

[DOI]

Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

Multilevel Adaptive Hashing.

[BibT_eX]

[DOI]

Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

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

[BibT_eX]

[DOI]

Christos Kaklamanis

Frank Thomson Leighton

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1988

Parallel hashing: an efficient implementation of shared memory.

[BibT_eX]

[DOI]

Eli Upfal

J. ACM, 1988

Competitive Snoopy Caching.

[BibT_eX]

[DOI]

Mark S. Manasse

Larry Rudolph

Daniel Dominic Sleator

Algorithmica, 1988

Bounds on the Cover Time (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987

Sharing memory in distributed systems : methods and applications.

[BibT_eX]

[DOI]

PhD thesis, 1987

Algorithms for the Compilation of Regular Expressions into PLAs.

[BibT_eX]

[DOI]

Howard Trickey

Jeffrey D. Ullman

Algorithmica, 1987

1986

Parallel Hashing-An Efficient Implementation of Shared Memory (Preliminary Version)

[BibT_eX]

[DOI]