2 Search Results for "Davis, Patrick"

Document
DOI: 10.4230/OASIcs.ATMOS.2019.11
Maximizing the Number of Rides Served for Dial-a-Ride

Authors: Barbara M. Anthony, Ricky Birnbaum, Sara Boyd, Ananya Christman, Christine Chung, Patrick Davis, Jigar Dhimar, and David Yuen

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract
We study a variation of offline Dial-a-Ride, where each request has not only a source and destination, but also a revenue that is earned for serving the request. We investigate this problem for the uniform metric space with uniform revenues. While we present a study on a simplified setting of the problem that has limited practical applications, this work provides the theoretical foundation for analyzing the more general forms of the problem. Since revenues are uniform the problem is equivalent to maximizing the number of served requests. We show that the problem is NP-hard and present a 2/3 approximation algorithm. We also show that a natural generalization of this algorithm has an approximation ratio at most 7/9.
Cite as

Barbara M. Anthony, Sara Boyd, Ricky Birnbaum, Ananya Christman, Christine Chung, Patrick Davis, Jigar Dhimar, and David Yuen. Maximizing the Number of Rides Served for Dial-a-Ride. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{anthony_et_al:OASIcs.ATMOS.2019.11,
  author =	{Anthony, Barbara M. and Birnbaum, Ricky and Boyd, Sara and Christman, Ananya and Chung, Christine and Davis, Patrick and Dhimar, Jigar and Yuen, David},
  title =	{{Maximizing the Number of Rides Served for Dial-a-Ride}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{11:1--11:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.11},
  URN =		{urn:nbn:de:0030-drops-114237},
  doi =		{10.4230/OASIcs.ATMOS.2019.11},
  annote =	{Keywords: dial-a-ride, revenue maximization, approximation algorithm, vehicle routing}
}
Document
DOI: 10.4230/LIPIcs.CSL.2012.137
A Negative Conjunctive Query is Easy if and only if it is Beta-Acyclic

Authors: Johann Brault-Baron

Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)

Abstract
It is known that the data complexity of a Conjunctive Query (CQ) is determined *only* by the way its variables are shared between atoms, reflected by its hypergraph. In particular, Yannakakis [Yannakakis VLDB'81,Beeri/Fagin/Maier/Yannakakis JACM'83] proved that a CQ is decidable in linear time when it is alpha-acyclic, i.e. its hypergraph is alpha-acyclic; Bagan et al. [Bagan/Durand/Grandjean CSL'07] even state: * Any CQ is decidable in linear time iff it is alpha-acyclic. (under certain hypotheses) (By linear time, we mean a query on a structure S can be decided in time O(|S|)) A natural question is: since the complexity of a *Negative* Conjunctive Query (NCQ), a conjunctive query where *all* atoms are negated, also only depends on its hypergraph, can we find a similar dichotomy in this case? To answer this question, we revisit a result of Ordyniak et al. --- that states that satisfiability of a beta-acyclic CNF formula is decidable in polynomial time --- by proving that some part of their procedure can be done in linear time. This implies, under an algorithmic hypothesis that is likely true: (precisely: one cannot decide whether a graph is triangle-free in time O(n²log n) where n is the number of vertices.) * Any NCQ is decidable in quasi-linear time iff it is beta-acyclic. (By quasi-linear time, we mean a query on a structure S can be decided in time O(|S|log|S|)) We extend the easiness result to 'Signed' Conjunctive Query (SCQ) where 'some' atoms are negated. This has great interest since using some negated atoms is natural in the frameworks of databases and CSP. Furthermore, it implies straightforwardly the following: * Any beta-acyclic existential first-order query is decidable in quasi-linear time.
Cite as

Johann Brault-Baron. A Negative Conjunctive Query is Easy if and only if it is Beta-Acyclic. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 137-151, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{braultbaron:LIPIcs.CSL.2012.137,
  author =	{Brault-Baron, Johann},
  title =	{{A Negative Conjunctive Query is Easy if and only if it is Beta-Acyclic}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{137--151},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{C\'{e}gielski, Patrick and Durand, Arnaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.137},
  URN =		{urn:nbn:de:0030-drops-36697},
  doi =		{10.4230/LIPIcs.CSL.2012.137},
  annote =	{Keywords: conjunctive query, hypergraph, beta-acyclicity, data complexity, Davis-Putnam procedure}
}
  • Refine by Author
  • 1 Anthony, Barbara M.
  • 1 Birnbaum, Ricky
  • 1 Boyd, Sara
  • 1 Brault-Baron, Johann
  • 1 Christman, Ananya
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Routing and network design problems

  • Refine by Keyword
  • 1 Davis-Putnam procedure
  • 1 approximation algorithm
  • 1 beta-acyclicity
  • 1 conjunctive query
  • 1 data complexity
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2012
  • 1 2019

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