Search Results

Documents authored by Roughgarden, Tim

Document
DOI: 10.4230/LIPIcs.AFT.2024.29
Transaction Fee Mechanism Design in a Post-MEV World

Authors: Maryam Bahrani, Pranav Garimidi, and Tim Roughgarden

Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)

Abstract
The incentive-compatibility properties of blockchain transaction fee mechanisms have been investigated with passive block producers that are motivated purely by the net rewards earned at the consensus layer. This paper introduces a model of active block producers that have their own private valuations for blocks (representing, for example, additional value derived from the application layer). The block producer surplus in our model can be interpreted as one of the more common colloquial meanings of the phrase "maximal extractable value (MEV)." We first prove that transaction fee mechanism design is fundamentally more difficult with active block producers than with passive ones: With active block producers, no non-trivial or approximately welfare-maximizing transaction fee mechanism can be incentive-compatible for both users and block producers. These results can be interpreted as a mathematical justification for augmenting transaction fee mechanisms with additional components such as order flow auctions, block producer competition, trusted hardware, or cryptographic techniques. We then consider a more fine-grained model of block production that more accurately reflects current practice, in which we distinguish the roles of "searchers" (who actively identify opportunities for value extraction from the application layer and compete for the right to take advantage of them) and "proposers" (who participate directly in the blockchain protocol and make the final choice of the published block). Searchers can effectively act as an "MEV oracle" for a transaction fee mechanism, thereby enlarging the design space. Here, we first consider a TFM that is inspired by how searchers have traditionally been incorporated into the block production process, with each transaction effectively sold off to a searcher through a first-price auction. We then explore the TFM design space with searchers more generally, and design a mechanism that circumvents our impossibility results for TFMs without searchers. Our mechanism (the "SAKA" mechanism) is incentive-compatible (for users, searchers, and the block producer), sybil-proof, and guarantees roughly 50% of the maximum-possible welfare when transaction sizes are small relative to block sizes. We conclude with a matching negative result: even when transaction sizes are small, no DSIC and sybil-proof deterministic TFM can guarantee more than 50% of the maximum-possible welfare.
Cite as

Maryam Bahrani, Pranav Garimidi, and Tim Roughgarden. Transaction Fee Mechanism Design in a Post-MEV World. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 29:1-29:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bahrani_et_al:LIPIcs.AFT.2024.29,
  author =	{Bahrani, Maryam and Garimidi, Pranav and Roughgarden, Tim},
  title =	{{Transaction Fee Mechanism Design in a Post-MEV World}},
  booktitle =	{6th Conference on Advances in Financial Technologies (AFT 2024)},
  pages =	{29:1--29:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-345-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{316},
  editor =	{B\"{o}hme, Rainer and Kiffer, Lucianna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.29},
  URN =		{urn:nbn:de:0030-drops-209658},
  doi =		{10.4230/LIPIcs.AFT.2024.29},
  annote =	{Keywords: MEV, Transaction Fee Mechanisms, Auctions}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.81
A Myersonian Framework for Optimal Liquidity Provision in Automated Market Makers

Authors: Jason Milionis, Ciamac C. Moallemi, and Tim Roughgarden

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
In decentralized finance ("DeFi"), automated market makers (AMMs) enable traders to programmatically exchange one asset for another. Such trades are enabled by the assets deposited by liquidity providers (LPs). The goal of this paper is to characterize and interpret the optimal (i.e., profit-maximizing) strategy of a monopolist liquidity provider, as a function of that LP’s beliefs about asset prices and trader behavior. We introduce a general framework for reasoning about AMMs based on a Bayesian-like belief inference framework, where LPs maintain an asset price estimate, which is updated by incorporating traders' price estimates. In this model, the market maker (i.e., LP) chooses a demand curve that specifies the quantity of a risky asset to be held at each dollar price. Traders arrive sequentially and submit a price bid that can be interpreted as their estimate of the risky asset price; the AMM responds to this submitted bid with an allocation of the risky asset to the trader, a payment that the trader must pay, and a revised internal estimate for the true asset price. We define an incentive-compatible (IC) AMM as one in which a trader’s optimal strategy is to submit its true estimate of the asset price, and characterize the IC AMMs as those with downward-sloping demand curves and payments defined by a formula familiar from Myerson’s optimal auction theory. We generalize Myerson’s virtual values, and characterize the profit-maximizing IC AMM. The optimal demand curve generally has a jump that can be interpreted as a "bid-ask spread," which we show is caused by a combination of adverse selection risk (dominant when the degree of information asymmetry is large) and monopoly pricing (dominant when asymmetry is small). This work opens up new research directions into the study of automated exchange mechanisms from the lens of optimal auction theory and iterative belief inference, using tools of theoretical computer science in a novel way.
Cite as

Jason Milionis, Ciamac C. Moallemi, and Tim Roughgarden. A Myersonian Framework for Optimal Liquidity Provision in Automated Market Makers. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 81:1-81:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{milionis_et_al:LIPIcs.ITCS.2024.81,
  author =	{Milionis, Jason and Moallemi, Ciamac C. and Roughgarden, Tim},
  title =	{{A Myersonian Framework for Optimal Liquidity Provision in Automated Market Makers}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{81:1--81:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.81},
  URN =		{urn:nbn:de:0030-drops-196094},
  doi =		{10.4230/LIPIcs.ITCS.2024.81},
  annote =	{Keywords: Posted-Price Mechanisms, Asset Exchange, Market Making, Automated Market Makers (AMMs), Blockchains, Decentralized Finance, Incentive Compatibility, Optimization}
}
Document
DOI: 10.4230/LIPIcs.AFT.2023.21
When Bidders Are DAOs

Authors: Maryam Bahrani, Pranav Garimidi, and Tim Roughgarden

Published in: LIPIcs, Volume 282, 5th Conference on Advances in Financial Technologies (AFT 2023)

Abstract
In a typical decentralized autonomous organization (DAO), people organize themselves into a group that is programmatically managed. DAOs can act as bidders in auctions (with ConstitutionDAO being one notable example), with a DAO’s bid typically treated by the auctioneer as if it had been submitted by an individual, without regard to any details of the internal DAO dynamics. The goal of this paper is to study auctions in which the bidders are DAOs. More precisely, we consider the design of two-level auctions in which the "participants" are groups of bidders rather than individuals. Bidders form DAOs to pool resources, but must then also negotiate the terms by which the DAO’s winnings are shared. We model the outcome of a DAO’s negotiations through an aggregation function (which aggregates DAO members' bids into a single group bid) and a budget-balanced cost-sharing mechanism (that determines DAO members' access to the DAO’s allocation and distributes the aggregate payment demanded from the DAO to its members). DAOs' bids are processed by a direct-revelation mechanism that has no knowledge of the DAO structure (and thus treats each DAO as an individual). Within this framework, we pursue two-level mechanisms that are incentive-compatible (with truthful bidding a dominant strategy for each member of each DAO) and approximately welfare-optimal. We prove that, even in the case of a single-item auction, the DAO dynamics hidden from the outer mechanism preclude incentive-compatible welfare maximization: No matter what the outer mechanism and the cost-sharing mechanisms used by DAOs, the welfare of the resulting two-level mechanism can be a ≈ ln n factor less than the optimal welfare (in the worst case over DAOs and valuation profiles). We complement this lower bound with a natural two-level mechanism that achieves a matching approximate welfare guarantee. This upper bound also extends to multi-item auctions in which individuals have additive valuations. Finally, we show that our positive results cannot be extended much further: Even in multi-item settings in which bidders have unit-demand valuations, truthful two-level mechanisms form a highly restricted class and as a consequence cannot guarantee any non-trivial approximation of the maximum social welfare.
Cite as

Maryam Bahrani, Pranav Garimidi, and Tim Roughgarden. When Bidders Are DAOs. In 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 282, pp. 21:1-21:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bahrani_et_al:LIPIcs.AFT.2023.21,
  author =	{Bahrani, Maryam and Garimidi, Pranav and Roughgarden, Tim},
  title =	{{When Bidders Are DAOs}},
  booktitle =	{5th Conference on Advances in Financial Technologies (AFT 2023)},
  pages =	{21:1--21:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-303-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{282},
  editor =	{Bonneau, Joseph and Weinberg, S. Matthew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2023.21},
  URN =		{urn:nbn:de:0030-drops-192108},
  doi =		{10.4230/LIPIcs.AFT.2023.21},
  annote =	{Keywords: Auctions, DAOs}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.17
FPT Algorithms for Finding Near-Cliques in c-Closed Graphs

Authors: Balaram Behera, Edin Husić, Shweta Jain, Tim Roughgarden, and C. Seshadhri

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
Finding large cliques or cliques missing a few edges is a fundamental algorithmic task in the study of real-world graphs, with applications in community detection, pattern recognition, and clustering. A number of effective backtracking-based heuristics for these problems have emerged from recent empirical work in social network analysis. Given the NP-hardness of variants of clique counting, these results raise a challenge for beyond worst-case analysis of these problems. Inspired by the triadic closure of real-world graphs, Fox et al. (SICOMP 2020) introduced the notion of c-closed graphs and proved that maximal clique enumeration is fixed-parameter tractable with respect to c. In practice, due to noise in data, one wishes to actually discover "near-cliques", which can be characterized as cliques with a sparse subgraph removed. In this work, we prove that many different kinds of maximal near-cliques can be enumerated in polynomial time (and FPT in c) for c-closed graphs. We study various established notions of such substructures, including k-plexes, complements of bounded-degeneracy and bounded-treewidth graphs. Interestingly, our algorithms follow relatively simple backtracking procedures, analogous to what is done in practice. Our results underscore the significance of the c-closed graph class for theoretical understanding of social network analysis.
Cite as

Balaram Behera, Edin Husić, Shweta Jain, Tim Roughgarden, and C. Seshadhri. FPT Algorithms for Finding Near-Cliques in c-Closed Graphs. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 17:1-17:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{behera_et_al:LIPIcs.ITCS.2022.17,
  author =	{Behera, Balaram and Husi\'{c}, Edin and Jain, Shweta and Roughgarden, Tim and Seshadhri, C.},
  title =	{{FPT Algorithms for Finding Near-Cliques in c-Closed Graphs}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{17:1--17:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.17},
  URN =		{urn:nbn:de:0030-drops-156130},
  doi =		{10.4230/LIPIcs.ITCS.2022.17},
  annote =	{Keywords: c-closed graph, dense subgraphs, FPT algorithm, enumeration algorithm, k-plex, Moon-Moser theorem}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2019.5
How Computer Science Informs Modern Auction Design (Invited Talk)

Authors: Tim Roughgarden

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
Over the last twenty years, computer science has relied on concepts borrowed from game theory and economics to reason about applications ranging from internet routing to real-time auctions for online advertising. More recently, ideas have increasingly flowed in the opposite direction, with concepts and techniques from computer science beginning to influence economic theory and practice. In this lecture, I will illustrate this point with a detailed case study of the 2016-2017 Federal Communications Commission incentive auction for repurposing wireless spectrum. Computer science techniques, ranging from algorithms for NP-hard problems to nondeterministic communication complexity, have played a critical role both in the design of the reverse auction (with the government procuring existing licenses from television broadcasters) and in the analysis of the forward auction (when the procured licenses sell to the highest bidder).
Cite as

Tim Roughgarden. How Computer Science Informs Modern Auction Design (Invited Talk). In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, p. 5:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{roughgarden:LIPIcs.FSTTCS.2019.5,
  author =	{Roughgarden, Tim},
  title =	{{How Computer Science Informs Modern Auction Design}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{5:1--5:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.5},
  URN =		{urn:nbn:de:0030-drops-115678},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.5},
  annote =	{Keywords: Game Theory, Auction Design, Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.55
Finding Cliques in Social Networks: A New Distribution-Free Model

Authors: Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We propose a new distribution-free model of social networks. Our definitions are motivated by one of the most universal signatures of social networks, triadic closure - the property that pairs of vertices with common neighbors tend to be adjacent. Our most basic definition is that of a c-closed graph, where for every pair of vertices u,v with at least c common neighbors, u and v are adjacent. We study the classic problem of enumerating all maximal cliques, an important task in social network analysis. We prove that this problem is fixed-parameter tractable with respect to c on c-closed graphs. Our results carry over to weakly c-closed graphs, which only require a vertex deletion ordering that avoids pairs of non-adjacent vertices with c common neighbors. Numerical experiments show that well-studied social networks tend to be weakly c-closed for modest values of c.
Cite as

Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein. Finding Cliques in Social Networks: A New Distribution-Free Model. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.ICALP.2018.55,
  author =	{Fox, Jacob and Roughgarden, Tim and Seshadhri, C. and Wei, Fan and Wein, Nicole},
  title =	{{Finding Cliques in Social Networks: A New Distribution-Free Model}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.55},
  URN =		{urn:nbn:de:0030-drops-90596},
  doi =		{10.4230/LIPIcs.ICALP.2018.55},
  annote =	{Keywords: Graph algorithms, social networks, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.26
Stability and Recovery for Independence Systems

Authors: Vaggos Chatziafratis, Tim Roughgarden, and Jan Vondrak

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Two genres of heuristics that are frequently reported to perform much better on "real-world" instances than in the worst case are greedy algorithms and local search algorithms. In this paper, we systematically study these two types of algorithms for the problem of maximizing a monotone submodular set function subject to downward-closed feasibility constraints. We consider perturbation-stable instances, in the sense of Bilu and Linial [11], and precisely identify the stability threshold beyond which these algorithms are guaranteed to recover the optimal solution. Byproducts of our work include the first definition of perturbation-stability for non-additive objective functions, and a resolution of the worst-case approximation guarantee of local search in p-extendible systems.
Cite as

Vaggos Chatziafratis, Tim Roughgarden, and Jan Vondrak. Stability and Recovery for Independence Systems. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chatziafratis_et_al:LIPIcs.ESA.2017.26,
  author =	{Chatziafratis, Vaggos and Roughgarden, Tim and Vondrak, Jan},
  title =	{{Stability and Recovery for Independence Systems}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.26},
  URN =		{urn:nbn:de:0030-drops-78423},
  doi =		{10.4230/LIPIcs.ESA.2017.26},
  annote =	{Keywords: Submodular, approximation, stability, Local Search, Greedy, p-systems}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.22
When Are Welfare Guarantees Robust?

Authors: Tim Roughgarden, Inbal Talgam-Cohen, and Jan Vondrák

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
Computational and economic results suggest that social welfare maximization and combinatorial auction design are much easier when bidders' valuations satisfy the "gross substitutes" condition. The goal of this paper is to evaluate rigorously the folklore belief that the main take-aways from these results remain valid in settings where the gross substitutes condition holds only approximately. We show that for valuations that pointwise approximate a gross substitutes valuation (in fact even a linear valuation), optimal social welfare cannot be approximated to within a subpolynomial factor and demand oracles cannot be simulated using a subexponential number of value queries. We then provide several positive results by imposing additional structure on the valuations (beyond gross substitutes), using a more stringent notion of approximation, and/or using more powerful oracle access to the valuations. For example, we prove that the performance of the greedy algorithm degrades gracefully for near-linear valuations with approximately decreasing marginal values; that with demand queries, approximate welfare guarantees for XOS valuations degrade gracefully for valuations that are pointwise close to XOS; and that the performance of the Kelso-Crawford auction degrades gracefully for valuations that are close to various subclasses of gross substitutes valuations.
Cite as

Tim Roughgarden, Inbal Talgam-Cohen, and Jan Vondrák. When Are Welfare Guarantees Robust?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{roughgarden_et_al:LIPIcs.APPROX-RANDOM.2017.22,
  author =	{Roughgarden, Tim and Talgam-Cohen, Inbal and Vondr\'{a}k, Jan},
  title =	{{When Are Welfare Guarantees Robust?}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{22:1--22:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.22},
  URN =		{urn:nbn:de:0030-drops-75714},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.22},
  annote =	{Keywords: Valuation (set) functions, gross substitutes, linearity, approximation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.78
The Complexity of the k-means Method

Authors: Tim Roughgarden and Joshua R. Wang

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
The k-means method is a widely used technique for clustering points in Euclidean space. While it is extremely fast in practice, its worst-case running time is exponential in the number of data points. We prove that the k-means method can implicitly solve PSPACE-complete problems, providing a complexity-theoretic explanation for its worst-case running time. Our result parallels recent work on the complexity of the simplex method for linear programming.
Cite as

Tim Roughgarden and Joshua R. Wang. The Complexity of the k-means Method. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 78:1-78:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{roughgarden_et_al:LIPIcs.ESA.2016.78,
  author =	{Roughgarden, Tim and Wang, Joshua R.},
  title =	{{The Complexity of the k-means Method}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{78:1--78:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.78},
  URN =		{urn:nbn:de:0030-drops-64191},
  doi =		{10.4230/LIPIcs.ESA.2016.78},
  annote =	{Keywords: k-means, PSPACE-complete}
}
Document
DOI: 10.4230/DagRep.4.9.30
Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372)

Authors: Marina-Florina Balcan, Bodo Manthey, Heiko Röglin, and Tim Roughgarden

Published in: Dagstuhl Reports, Volume 4, Issue 9 (2015)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14372 "Analysis of Algorithms Beyond the Worst Case". The theory of algorithms has traditionally focused on worst-case analysis. This focus has led to both a deep theory and many beautiful and useful algorithms. However, there are a number of important problems and algorithms for which worst-case analysis does not provide useful or empirically accurate results. This is due to the fact that worst-case inputs are often rather contrived and occur hardly ever in practical applications. Only in recent years a paradigm shift towards a more realistic and robust algorithmic theory has been initiated. The development of a more realistic theory hinges on finding models that measure the performance of an algorithm not only by its worst-case behavior but rather by its behavior on "typical" inputs. In this seminar, we discussed various recent theoretical models and results that go beyond worst-case analysis. The seminar helped to consolidate the research and to foster collaborations among the researchers working in the different branches of analysis of algorithms beyond the worst case.
Cite as

Marina-Florina Balcan, Bodo Manthey, Heiko Röglin, and Tim Roughgarden. Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372). In Dagstuhl Reports, Volume 4, Issue 9, pp. 30-49, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{balcan_et_al:DagRep.4.9.30,
  author =	{Balcan, Marina-Florina and Manthey, Bodo and R\"{o}glin, Heiko and Roughgarden, Tim},
  title =	{{Analysis of Algorithms Beyond the Worst Case (Dagstuhl Seminar 14372)}},
  pages =	{30--49},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{4},
  number =	{9},
  editor =	{Balcan, Marina-Florina and Manthey, Bodo and R\"{o}glin, Heiko and Roughgarden, Tim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.9.30},
  URN =		{urn:nbn:de:0030-drops-48829},
  doi =		{10.4230/DagRep.4.9.30},
  annote =	{Keywords: analysis of algorithms, probabilistic analysis, smoothed analysis, approximation stability, machine learning}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact