3 Search Results for "Li, Bo"


Document
Short Paper
Impacts of Catchments Derived from Fine-Grained Mobility Data on Spatial Accessibility (Short Paper)

Authors: Alexander Michels, Jinwoo Park, Bo Li, Jeon-Young Kang, and Shaowen Wang

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)


Abstract
Spatial accessibility is a powerful tool for understanding how access to important services and resources varies across space. While spatial accessibility methods traditionally rely on origin-destination matrices between centroids of administrative zones, recent work has examined creating polygonal catchments - areas within a travel-time threshold - from point-based fine-grained mobility data. In this paper, we investigate the difference between the convex hull and alpha shape algorithms for determining catchment areas and how this affects the results of spatial accessibility analyses. Our analysis shows that the choice of how we define a catchment produces differences in the measured accessibility which correlate with social vulnerability. These findings highlight the importance of evaluating and communicating minor methodological choices in spatial accessibility analyses.

Cite as

Alexander Michels, Jinwoo Park, Bo Li, Jeon-Young Kang, and Shaowen Wang. Impacts of Catchments Derived from Fine-Grained Mobility Data on Spatial Accessibility (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 52:1-52:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{michels_et_al:LIPIcs.GIScience.2023.52,
  author =	{Michels, Alexander and Park, Jinwoo and Li, Bo and Kang, Jeon-Young and Wang, Shaowen},
  title =	{{Impacts of Catchments Derived from Fine-Grained Mobility Data on Spatial Accessibility}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{52:1--52:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.52},
  URN =		{urn:nbn:de:0030-drops-189470},
  doi =		{10.4230/LIPIcs.GIScience.2023.52},
  annote =	{Keywords: Spatial accessibility, alpha shape, convex hull, cyberGIS, social vulnerability}
}
Document
Brief Announcement
Brief Announcement: Bayesian Auctions with Efficient Queries

Authors: Jing Chen, Bo Li, Yingkai Li, and Pinyan Lu

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


Abstract
Generating good revenue is one of the most important problems in Bayesian auction design, and many (approximately) optimal dominant-strategy incentive compatible (DSIC) Bayesian mechanisms have been constructed for various auction settings. However, most existing studies do not consider the complexity for the seller to carry out the mechanism. It is assumed that the seller knows "each single bit" of the distributions and is able to optimize perfectly based on the entire distributions. Unfortunately this is a strong assumption and may not hold in reality: for example, when the value distributions have exponentially large supports or do not have succinct representations. In this work we consider, for the first time, the query complexity of Bayesian mechanisms. We only allow the seller to have limited oracle accesses to the players' value distributions, via quantile queries and value queries. For a large class of auction settings, we prove logarithmic lower-bounds for the query complexity for any DSIC Bayesian mechanism to be of any constant approximation to the optimal revenue. For single-item auctions and multi-item auctions with unit-demand or additive valuation functions, we prove tight upper-bounds via efficient query schemes, without requiring the distributions to be regular or have monotone hazard rate. Thus, in those auction settings the seller needs to access much less than the full distributions in order to achieve approximately optimal revenue.

Cite as

Jing Chen, Bo Li, Yingkai Li, and Pinyan Lu. Brief Announcement: Bayesian Auctions with Efficient Queries. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 108:1-108:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2018.108,
  author =	{Chen, Jing and Li, Bo and Li, Yingkai and Lu, Pinyan},
  title =	{{Brief Announcement: Bayesian Auctions with Efficient Queries}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{108:1--108:4},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.108},
  URN =		{urn:nbn:de:0030-drops-91124},
  doi =		{10.4230/LIPIcs.ICALP.2018.108},
  annote =	{Keywords: The complexity of Bayesian mechanisms, quantile queries, value queries}
}
Document
Efficient Approximations for the Online Dispersion Problem

Authors: Jing Chen, Bo Li, and Yingkai Li

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)


Abstract
The dispersion problem has been widely studied in computational geometry and facility location, and is closely related to the packing problem. The goal is to locate n points (e.g., facilities or persons) in a k-dimensional polytope, so that they are far away from each other and from the boundary of the polytope. In many real-world scenarios however, the points arrive and depart at different times, and decisions must be made without knowing future events. Therefore we study, for the first time in the literature, the online dispersion problem in Euclidean space. There are two natural objectives when time is involved: the all-time worst-case (ATWC) problem tries to maximize the minimum distance that ever appears at any time; and the cumulative distance (CD) problem tries to maximize the integral of the minimum distance throughout the whole time interval. Interestingly, the online problems are highly non-trivial even on a segment. For cumulative distance, this remains the case even when the problem is time-dependent but offline, with all the arriving and departure times given in advance. For the online ATWC problem on a segment, we construct a deterministic polynomial-time algorithm which is (2ln2+epsilon)-competitive, where epsilon>0 can be arbitrarily small and the algorithm's running time is polynomial in 1/epsilon. We show this algorithm is actually optimal. For the same problem in a square, we provide a 1.591-competitive algorithm and a 1.183 lower-bound. Furthermore, for arbitrary k-dimensional polytopes with k>=2, we provide a 2/(1-epsilon)-competitive algorithm and a 7/6 lower-bound. All our lower-bounds come from the structure of the online problems and hold even when computational complexity is not a concern. Interestingly, for the offline CD problem in arbitrary k-dimensional polytopes, we provide a polynomial-time black-box reduction to the online ATWC problem, and the resulting competitive ratio increases by a factor of at most 2. Our techniques also apply to online dispersion problems with different boundary conditions.

Cite as

Jing Chen, Bo Li, and Yingkai Li. Efficient Approximations for the Online Dispersion Problem. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2017.11,
  author =	{Chen, Jing and Li, Bo and Li, Yingkai},
  title =	{{Efficient Approximations for the Online Dispersion Problem}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.11},
  URN =		{urn:nbn:de:0030-drops-74002},
  doi =		{10.4230/LIPIcs.ICALP.2017.11},
  annote =	{Keywords: dispersion, online algorithms, geometric optimization, packing, competitive algorithms}
}
  • Refine by Author
  • 3 Li, Bo
  • 2 Chen, Jing
  • 2 Li, Yingkai
  • 1 Kang, Jeon-Young
  • 1 Lu, Pinyan
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Earth and atmospheric sciences
  • 1 Applied computing → Health informatics
  • 1 Applied computing → Transportation
  • 1 Theory of computation → Algorithmic game theory and mechanism design

  • Refine by Keyword
  • 1 Spatial accessibility
  • 1 The complexity of Bayesian mechanisms
  • 1 alpha shape
  • 1 competitive algorithms
  • 1 convex hull
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2017
  • 1 2018
  • 1 2023

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