8 Search Results for "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-dev.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
Invited Talk
DOI: 10.4230/LIPIcs.CPM.2022.3
Compact Text Indexing for Advanced Pattern Matching Problems: Parameterized, Order-Isomorphic, 2D, etc. (Invited Talk)

Authors: Sharma V. Thankachan

Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)

Abstract
In the past two decades, we have witnessed the design of various compact data structures for pattern matching over an indexed text [Navarro, 2016]. Popular indexes like the FM-index [Paolo Ferragina and Giovanni Manzini, 2005], compressed suffix arrays/trees [Roberto Grossi and Jeffrey Scott Vitter, 2005; Kunihiko Sadakane, 2007], the recent r-index [Travis Gagie et al., 2020; Takaaki Nishimoto and Yasuo Tabei, 2021], etc., capture the key functionalities of classic suffix arrays/trees [Udi Manber and Eugene W. Myers, 1993; Peter Weiner, 1973] in compact space. Mostly, they rely on the Burrows-Wheeler Transform (BWT) and its associated operations [Burrows and Wheeler, 1994]. However, compactly encoding some advanced suffix tree (ST) variants, like parameterized ST [Brenda S. Baker, 1993; S. Rao Kosaraju, 1995; Juan Mendivelso et al., 2020], order-isomorphic/preserving ST [Maxime Crochemore et al., 2016], two-dimensional ST [Raffaele Giancarlo, 1995; Dong Kyue Kim et al., 1998], etc. [Sung Gwan Park et al., 2019; Tetsuo Shibuya, 2000]- collectively known as suffix trees with missing suffix links [Richard Cole and Ramesh Hariharan, 2003], has been challenging. The previous techniques are not easily extendable because these variants do not hold some structural properties of the standard ST that enable compression. However, some limited progress has been made in these directions recently [Arnab Ganguly et al., 2017; Travis Gagie et al., 2017; Gianni Decaroli et al., 2017; Dhrumil Patel and Rahul Shah, 2021; Arnab Ganguly et al., 2021; Sung{-}Hwan Kim and Hwan{-}Gue Cho, 2021; Sung{-}Hwan Kim and Hwan{-}Gue Cho, 2021; Arnab Ganguly et al., 2017; Arnab Ganguly et al., 2022; Arnab Ganguly et al., 2021]. This talk will briefly survey them and highlight some interesting open problems.
Cite as

Sharma V. Thankachan. Compact Text Indexing for Advanced Pattern Matching Problems: Parameterized, Order-Isomorphic, 2D, etc. (Invited Talk). In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 3:1-3:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{thankachan:LIPIcs.CPM.2022.3,
  author =	{Thankachan, Sharma V.},
  title =	{{Compact Text Indexing for Advanced Pattern Matching Problems: Parameterized, Order-Isomorphic, 2D, etc.}},
  booktitle =	{33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)},
  pages =	{3:1--3:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-234-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{223},
  editor =	{Bannai, Hideo and Holub, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.3},
  URN =		{urn:nbn:de:0030-drops-161300},
  doi =		{10.4230/LIPIcs.CPM.2022.3},
  annote =	{Keywords: Text Indexing, Suffix Trees, String Matching}
}
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-dev.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/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-dev.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}
}
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-dev.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
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.44
Is This Statement About A Place? Comparing two perspectives (Short Paper)

Authors: Alan M. MacEachren, Richard Caneba, Hanzhou Chen, Harrison Cole, Emily Domanico, Nicholas Triozzi, Fangcao Xu, and Liping Yang

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
Text often includes references to places by name; in prior work, more than 20% of a sample of event-related tweets were found to include place names. Research has addressed the challenge of leveraging the geographic data reflected in text statements, with well-developed methods to recognize location mentions in text and related work on automated toponym resolution (deciding which place in the world is meant by a place name). A core issue that remains is to distinguish between text that mentions a place or places and text that is about a place or places. This paper presents the first step in research to address this challenge. The research reported here sets the conceptual and practical groundwork for subsequent supervised machine learning research; that research will leverage human-produced training data, for which a judgment is made about whether a statement is or is not about a place (or places), to train computational methods to do this classification for large volumes of text. The research step presented here focuses on three questions: (1) what kinds of entities are typically conceptualized as places, (2) what features of a statement prompt the reader to judge a statement to be about a place (or not about a place) and (3) how do judgments of whether or not a statement is about a place compare between a group of experts who have studied the concept of "place" from a geographic perspective and a cross-section of individuals recruited through a crowdsourcing platform to make these judgments.
Cite as

Alan M. MacEachren, Richard Caneba, Hanzhou Chen, Harrison Cole, Emily Domanico, Nicholas Triozzi, Fangcao Xu, and Liping Yang. Is This Statement About A Place? Comparing two perspectives (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 44:1-44:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{maceachren_et_al:LIPIcs.GISCIENCE.2018.44,
  author =	{MacEachren, Alan M. and Caneba, Richard and Chen, Hanzhou and Cole, Harrison and Domanico, Emily and Triozzi, Nicholas and Xu, Fangcao and Yang, Liping},
  title =	{{Is This Statement About A Place? Comparing two perspectives}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{44:1--44:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.44},
  URN =		{urn:nbn:de:0030-drops-93720},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.44},
  annote =	{Keywords: geographic information retrieval, spatial language, crowdsourcing}
}
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-dev.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-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.33},
  URN =		{urn:nbn:de:0030-drops-149216},
  doi =		{10.4230/DagSemRep.33},
}
  • Refine by Author
  • 5 Cole, Richard
  • 2 Mayr, Ernst W.
  • 2 Meyer auf der Heide, Friedhelm
  • 1 Agarwal, Ishan
  • 1 Babaioff, Moshe
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Natural language processing
  • 1 Information systems → Information retrieval
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Matchings and factors
  • 1 Theory of computation → Market equilibria
  • Show More...

  • Refine by Keyword
  • 1 Amortized Analysis
  • 1 Asynchronous Tatonnement
  • 1 Fisher Market
  • 1 Market Equilibrium
  • 1 Non-quasi-linear agents
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 2 2018
  • 1 1992
  • 1 1993
  • 1 2019
  • 1 2021
  • Show More...

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