Search Results

Documents authored by Cole, Richard

Found 2 Possible Name Variants:

Cole, Richard L.

Document
DOI: 10.4230/DagRep.9.7.24
Data Series Management (Dagstuhl Seminar 19282)

Authors: Anthony Bagnall, Richard L. Cole, Themis Palpanas, and Kostas Zoumpatianos

Published in: Dagstuhl Reports, Volume 9, Issue 7 (2020)

Abstract
We now witness a very strong interest by users across different domains on data series (a.k.a. time series) management. It is not unusual for industrial applications that produce data series to involve numbers of sequences (or subsequences) in the order of billions (i.e., multiple TBs). As a result, analysts are unable to handle the vast amounts of data series that they have to manage and process. The goal of this seminar is to enable researchers and practitioners to exchange ideas and foster collaborations in the topic of data series management and identify the corresponding open research directions. The main questions answered are the following: i) What are the data series management needs across various domains and what are the shortcomings of current systems, ii) How can we use machine learning to optimize our current data systems, and how can these systems help in machine learning pipelines? iii) How can visual analytics assist the process of analyzing big data series collections? The seminar focuses on the following key topics related to data series management: 1)Data series storage and access paterns, 2) Query optimization, 3) Machine learning and data mining for data serie, 4) Visualization for data series exploration, 5) Applications in multiple domains.
Cite as

Anthony Bagnall, Richard L. Cole, Themis Palpanas, and Kostas Zoumpatianos. Data Series Management (Dagstuhl Seminar 19282). In Dagstuhl Reports, Volume 9, Issue 7, pp. 24-39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{bagnall_et_al:DagRep.9.7.24,
  author =	{Bagnall, Anthony and Cole, Richard L. and Palpanas, Themis and Zoumpatianos, Kostas},
  title =	{{Data Series Management (Dagstuhl Seminar 19282)}},
  pages =	{24--39},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{7},
  editor =	{Bagnall, Anthony and Cole, Richard L. and Palpanas, Themis and Zoumpatianos, Kostas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.7.24},
  URN =		{urn:nbn:de:0030-drops-116349},
  doi =		{10.4230/DagRep.9.7.24},
  annote =	{Keywords: data series; time series; sequences; management; indexing; analytics; machine learning; mining; visualization}
}

Cole, Richard

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.8
Stable Matching: Choosing Which Proposals to Make

Authors: Ishan Agarwal and Richard Cole

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
To guarantee all agents are matched in general, the classic Deferred Acceptance algorithm needs complete preference lists. In practice, preference lists are short, yet stable matching still works well. This raises two questions: - Why does it work well? - Which proposals should agents include in their preference lists? We study these questions in a model, introduced by Lee [Lee, 2016], with preferences based on correlated cardinal utilities: these utilities are based on common public ratings of each agent together with individual private adjustments. Lee showed that for suitable utility functions, in large markets, with high probability, for most agents, all stable matchings yield similar valued utilities. By means of a new analysis, we strengthen Lee’s result, showing that in large markets, with high probability, for all but the agents with the lowest public ratings, all stable matchings yield similar valued utilities. We can then deduce that for all but the agents with the lowest public ratings, each agent has an easily identified length O(log n) preference list that includes all of its stable matches, addressing the second question above. We note that this identification uses an initial communication phase. We extend these results to settings where the two sides have unequal numbers of agents, to many-to-one settings, e.g. employers and workers, and we also show the existence of an ε-Bayes-Nash equilibrium in which every agent makes relatively few proposals. These results all rely on a new technique for sidestepping the conditioning between the tentative matching events that occur over the course of a run of the Deferred Acceptance algorithm. We complement these theoretical results with an experimental study.
Cite as

Ishan Agarwal and Richard Cole. Stable Matching: Choosing Which Proposals to Make. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ICALP.2023.8,
  author =	{Agarwal, Ishan and Cole, Richard},
  title =	{{Stable Matching: Choosing Which Proposals to Make}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.8},
  URN =		{urn:nbn:de:0030-drops-180603},
  doi =		{10.4230/LIPIcs.ICALP.2023.8},
  annote =	{Keywords: Stable matching, randomized analysis}
}
Document
Extended Abstract
DOI: 10.4230/LIPIcs.ITCS.2021.84
Non-Quasi-Linear Agents in Quasi-Linear Mechanisms (Extended Abstract)

Authors: Moshe Babaioff, Richard Cole, Jason Hartline, Nicole Immorlica, and Brendan Lucier

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
Mechanisms with money are commonly designed under the assumption that agents are quasi-linear, meaning they have linear disutility for spending money. We study the implications when agents with non-linear (specifically, convex) disutility for payments participate in mechanisms designed for quasi-linear agents. We first show that any mechanism that is truthful for quasi-linear buyers has a simple best response function for buyers with non-linear disutility from payments, in which each bidder simply scales down her value for each potential outcome by a fixed factor, equal to her target return on investment (ROI). We call such a strategy ROI-optimal. We prove the existence of a Nash equilibrium in which agents use ROI-optimal strategies for a general class of allocation problems. Motivated by online marketplaces, we then focus on simultaneous second-price auctions for additive bidders and show that all ROI-optimal equilibria in this setting achieve constant-factor approximations to suitable welfare and revenue benchmarks.
Cite as

Moshe Babaioff, Richard Cole, Jason Hartline, Nicole Immorlica, and Brendan Lucier. Non-Quasi-Linear Agents in Quasi-Linear Mechanisms (Extended Abstract). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, p. 84:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{babaioff_et_al:LIPIcs.ITCS.2021.84,
  author =	{Babaioff, Moshe and Cole, Richard and Hartline, Jason and Immorlica, Nicole and Lucier, Brendan},
  title =	{{Non-Quasi-Linear Agents in Quasi-Linear Mechanisms}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{84:1--84:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.84},
  URN =		{urn:nbn:de:0030-drops-136230},
  doi =		{10.4230/LIPIcs.ITCS.2021.84},
  annote =	{Keywords: Return on investment, Non-quasi-linear agents, Transferable Welfare, Simultaneous Second-Price Auctions}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.18
Amortized Analysis of Asynchronous Price Dynamics

Authors: Yun Kuen Cheung and Richard Cole

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
We extend a recently developed framework for analyzing asynchronous coordinate descent algorithms to show that an asynchronous version of tatonnement, a fundamental price dynamic widely studied in general equilibrium theory, converges toward a market equilibrium for Fisher markets with CES utilities or Leontief utilities, for which tatonnement is equivalent to coordinate descent.
Cite as

Yun Kuen Cheung and Richard Cole. Amortized Analysis of Asynchronous Price Dynamics. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cheung_et_al:LIPIcs.ESA.2018.18,
  author =	{Cheung, Yun Kuen and Cole, Richard},
  title =	{{Amortized Analysis of Asynchronous Price Dynamics}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.18},
  URN =		{urn:nbn:de:0030-drops-94812},
  doi =		{10.4230/LIPIcs.ESA.2018.18},
  annote =	{Keywords: Asynchronous Tatonnement, Fisher Market, Market Equilibrium, Amortized Analysis}
}
Document
DOI: 10.4230/DagSemRep.72
Parallel and Distributed Algorithms (Dagstuhl Seminar 9337)

Authors: Richard Cole, Ernst W. Mayr, and Friedhelm Meyer auf der Heide

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Richard Cole, Ernst W. Mayr, and Friedhelm Meyer auf der Heide. Parallel and Distributed Algorithms (Dagstuhl Seminar 9337). Dagstuhl Seminar Report 72, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1993)

Copy BibTex To Clipboard

@TechReport{cole_et_al:DagSemRep.72,
  author =	{Cole, Richard and Mayr, Ernst W. and Meyer auf der Heide, Friedhelm},
  title =	{{Parallel and Distributed Algorithms (Dagstuhl Seminar 9337)}},
  pages =	{1--24},
  ISSN =	{1619-0203},
  year =	{1993},
  type = 	{Dagstuhl Seminar Report},
  number =	{72},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.72},
  URN =		{urn:nbn:de:0030-drops-149606},
  doi =		{10.4230/DagSemRep.72},
}
Document
DOI: 10.4230/DagSemRep.33
Parallel and Distributed Algorithms (Dagstuhl Seminar 9210)

Authors: Richard Cole, Ernst W. Mayr, and Friedhelm Meyer auf der Heide

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Richard Cole, Ernst W. Mayr, and Friedhelm Meyer auf der Heide. Parallel and Distributed Algorithms (Dagstuhl Seminar 9210). Dagstuhl Seminar Report 33, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1992)

Copy BibTex To Clipboard

@TechReport{cole_et_al:DagSemRep.33,
  author =	{Cole, Richard and Mayr, Ernst W. and Meyer auf der Heide, Friedhelm},
  title =	{{Parallel and Distributed Algorithms (Dagstuhl Seminar 9210)}},
  pages =	{1--23},
  ISSN =	{1619-0203},
  year =	{1992},
  type = 	{Dagstuhl Seminar Report},
  number =	{33},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.33},
  URN =		{urn:nbn:de:0030-drops-149216},
  doi =		{10.4230/DagSemRep.33},
}
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 About DROPS Imprint Privacy Contact