6 Search Results for "Martin, Henry"

Document
DOI: 10.4230/LIPIcs.GIScience.2023.11
Benchmarking Regression Models Under Spatial Heterogeneity

Authors: Nina Wiedemann, Henry Martin, and René Westerholt

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

Abstract
Machine learning methods have recently found much application on spatial data, for example in weather forecasting, traffic prediction, and soil analysis. At the same time, methods from spatial statistics were developed over the past decades to explicitly account for spatial structuring in analytical and inference tasks. In the light of this duality of having both types of methods available, we explore the following question: Under what circumstances are local, spatially-explicit models preferable over machine learning models that do not incorporate spatial structure explicitly in their specification? Local models are typically used to capture spatial non-stationarity. Thus, we study the effect of strength and type of spatial heterogeneity, which may originate from non-stationarity of a process itself or from heterogeneous noise, on the performance of different linear and non-linear, local and global machine learning and regression models. The results suggest that it is necessary to assess the performance of linear local models on an independent hold-out dataset, since models may overfit under certain conditions. We further show that local models are advantageous in settings with small sample size and high degrees of spatial heterogeneity. Our findings allow deriving model selection criteria, which are validated in benchmarking experiments on five well-known spatial datasets.
Cite as

Nina Wiedemann, Henry Martin, and René Westerholt. Benchmarking Regression Models Under Spatial Heterogeneity. In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{wiedemann_et_al:LIPIcs.GIScience.2023.11,
  author =	{Wiedemann, Nina and Martin, Henry and Westerholt, Ren\'{e}},
  title =	{{Benchmarking Regression Models Under Spatial Heterogeneity}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{11:1--11:15},
  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.11},
  URN =		{urn:nbn:de:0030-drops-189064},
  doi =		{10.4230/LIPIcs.GIScience.2023.11},
  annote =	{Keywords: spatial machine learning, spatial non-stationarity, Geographically Weighted Regression, local models, geostatistics}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.52
A Tight Competitive Ratio for Online Submodular Welfare Maximization

Authors: Amit Ganz, Pranav Nuti, and Roy Schwartz

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
In this paper we consider the online Submodular Welfare (SW) problem. In this problem we are given n bidders each equipped with a general non-negative (not necessarily monotone) submodular utility and m items that arrive online. The goal is to assign each item, once it arrives, to a bidder or discard it, while maximizing the sum of utilities. When an adversary determines the items' arrival order we present a simple randomized algorithm that achieves a tight competitive ratio of 1/4. The algorithm is a specialization of an algorithm due to [Harshaw-Kazemi-Feldman-Karbasi MOR`22], who presented the previously best known competitive ratio of 3-2√2≈ 0.171573 to the problem. When the items' arrival order is uniformly random, we present a competitive ratio of ≈ 0.27493, improving the previously known 1/4 guarantee. Our approach for the latter result is based on a better analysis of the (offline) Residual Random Greedy (RRG) algorithm of [Buchbinder-Feldman-Naor-Schwartz SODA`14], which we believe might be of independent interest.
Cite as

Amit Ganz, Pranav Nuti, and Roy Schwartz. A Tight Competitive Ratio for Online Submodular Welfare Maximization. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ganz_et_al:LIPIcs.ESA.2023.52,
  author =	{Ganz, Amit and Nuti, Pranav and Schwartz, Roy},
  title =	{{A Tight Competitive Ratio for Online Submodular Welfare Maximization}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{52:1--52:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.52},
  URN =		{urn:nbn:de:0030-drops-187052},
  doi =		{10.4230/LIPIcs.ESA.2023.52},
  annote =	{Keywords: Online Algorithms, Submodular Maximization, Welfare Maximization, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.69
An Improved Approximation Algorithm for the Max-3-Section Problem

Authors: Dor Katzelnick, Aditya Pillai, Roy Schwartz, and Mohit Singh

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We consider the Max--Section problem, where we are given an undirected graph G=(V,E)equipped with non-negative edge weights w: E → R_+ and the goal is to find a partition of V into three equisized parts while maximizing the total weight of edges crossing between different parts. Max-3-Section is closely related to other well-studied graph partitioning problems, e.g., Max-Cut, Max-3-Cut, and Max-Bisection. We present a polynomial time algorithm achieving an approximation of 0.795, that improves upon the previous best known approximation of 0.673. The requirement of multiple parts that have equal sizes renders Max-3-Section much harder to cope with compared to, e.g., Max-Bisection. We show a new algorithm that combines the existing approach of Lassere hierarchy along with a random cut strategy that suffices to give our result.
Cite as

Dor Katzelnick, Aditya Pillai, Roy Schwartz, and Mohit Singh. An Improved Approximation Algorithm for the Max-3-Section Problem. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 69:1-69:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{katzelnick_et_al:LIPIcs.ESA.2023.69,
  author =	{Katzelnick, Dor and Pillai, Aditya and Schwartz, Roy and Singh, Mohit},
  title =	{{An Improved Approximation Algorithm for the Max-3-Section Problem}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{69:1--69:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.69},
  URN =		{urn:nbn:de:0030-drops-187229},
  doi =		{10.4230/LIPIcs.ESA.2023.69},
  annote =	{Keywords: Approximation Algorithms, Semidefinite Programming, Max-Cut, Max-Bisection}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.II.4
A Clustering-Based Framework for Individual Travel Behaviour Change Detection

Authors: Ye Hong, Yanan Xin, Henry Martin, Dominik Bucher, and Martin Raubal

Published in: LIPIcs, Volume 208, 11th International Conference on Geographic Information Science (GIScience 2021) - Part II

Abstract
The emergence of passively and continuously recorded movement data offers new opportunities to study the long-term change of individual travel behaviour from data-driven perspectives. This study proposes a clustering-based framework to identify travel behaviour patterns and detect potential change periods on the individual level. First, we extract important trips that depict individual characteristic movement. Then, considering trip mode, trip distance, and trip duration as travel behaviour dimensions, we measure the similarities of trips and group them into clusters using hierarchical clustering. The trip clusters represent dimensions of travel behaviours, and the change of their relative proportions over time reflect the development of travel preferences. We use two different methods to detect changes in travel behaviour patterns: the Herfindahl-Hirschman index-based method and the sliding window-based method. The framework is tested using data from a large-scale longitudinal GPS tracking data study in which participants had access to a Mobility-as-a-Service (MaaS) offer. The methods successfully identify significant travel behaviour changes for users. Moreover, we analyse the impact of the MaaS offer on individual travel behaviours with the obtained change information. The proposed framework for behaviour change detection provides valuable insights for travel demand management and evaluating people’s reactions to sustainable mobility options.
Cite as

Ye Hong, Yanan Xin, Henry Martin, Dominik Bucher, and Martin Raubal. A Clustering-Based Framework for Individual Travel Behaviour Change Detection. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part II. Leibniz International Proceedings in Informatics (LIPIcs), Volume 208, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hong_et_al:LIPIcs.GIScience.2021.II.4,
  author =	{Hong, Ye and Xin, Yanan and Martin, Henry and Bucher, Dominik and Raubal, Martin},
  title =	{{A Clustering-Based Framework for Individual Travel Behaviour Change Detection}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part II},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-208-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{208},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.II.4},
  URN =		{urn:nbn:de:0030-drops-147635},
  doi =		{10.4230/LIPIcs.GIScience.2021.II.4},
  annote =	{Keywords: Human mobility, Travel behaviour, Change detection, Trip clustering}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.I.2
Estimation of Moran’s I in the Context of Uncertain Mobile Sensor Measurements

Authors: Dominik Bucher, Henry Martin, David Jonietz, Martin Raubal, and René Westerholt

Published in: LIPIcs, Volume 177, 11th International Conference on Geographic Information Science (GIScience 2021) - Part I (2020)

Abstract
Measures of spatial autocorrelation like Moran’s I do not take into account information about the reliability of observations. In a context of mobile sensors, however, this is an important aspect to consider. Mobile sensors record data asynchronously and capture different contexts, which leads to considerable heterogeneity. In this paper we propose two different ways to integrate the reliability of observations with Moran’s I. These proposals are tested in the light of two case studies, one based on real temperatures and movement data and the other using synthetic data. The results show that the way reliability information is incorporated into the Moran’s I estimates has a strong impact on how the measure responds to volatile available information. It is shown that absolute reliability information is much less powerful in addressing the problem of differing contexts than relative concepts that give more weight to more reliable observations, regardless of the general degree of uncertainty. The results presented are seen as an important stimulus for the discourse on spatial autocorrelation measures in the light of uncertainties.
Cite as

Dominik Bucher, Henry Martin, David Jonietz, Martin Raubal, and René Westerholt. Estimation of Moran’s I in the Context of Uncertain Mobile Sensor Measurements. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part I. Leibniz International Proceedings in Informatics (LIPIcs), Volume 177, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bucher_et_al:LIPIcs.GIScience.2021.I.2,
  author =	{Bucher, Dominik and Martin, Henry and Jonietz, David and Raubal, Martin and Westerholt, Ren\'{e}},
  title =	{{Estimation of Moran’s I in the Context of Uncertain Mobile Sensor Measurements}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part I},
  pages =	{2:1--2:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-166-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{177},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.I.2},
  URN =		{urn:nbn:de:0030-drops-130375},
  doi =		{10.4230/LIPIcs.GIScience.2021.I.2},
  annote =	{Keywords: mobile sensors, Moran’s I, uncertainty, probabilistic forecasting}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.12
A Phase Transition in Minesweeper

Authors: Ross Dempsey and Charles Guinn

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
We study the average-case complexity of the classic Minesweeper game in which players deduce the locations of mines on a two-dimensional lattice. Playing Minesweeper is known to be co-NP-complete. We show empirically that Minesweeper exhibits a phase transition analogous to the well-studied SAT phase transition. Above the critical mine density it becomes almost impossible to play Minesweeper by logical inference. We use a reduction to Boolean unsatisfiability to characterize the hardness of Minesweeper instances, and show that the hardness peaks at the phase transition. Furthermore, we demonstrate algorithmic barriers at the phase transition for polynomial-time approaches to Minesweeper inference. Finally, we comment on expectations for the asymptotic behavior of the phase transition.
Cite as

Ross Dempsey and Charles Guinn. A Phase Transition in Minesweeper. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 12:1-12:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dempsey_et_al:LIPIcs.FUN.2021.12,
  author =	{Dempsey, Ross and Guinn, Charles},
  title =	{{A Phase Transition in Minesweeper}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{12:1--12:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.12},
  URN =		{urn:nbn:de:0030-drops-127735},
  doi =		{10.4230/LIPIcs.FUN.2021.12},
  annote =	{Keywords: Complexity of Games, Minesweeper}
}
  • Refine by Author
  • 3 Martin, Henry
  • 2 Bucher, Dominik
  • 2 Raubal, Martin
  • 2 Schwartz, Roy
  • 2 Westerholt, René
  • Show More...

  • Refine by Classification
  • 2 Information systems → Geographic information systems
  • 1 Applied computing → Earth and atmospheric sciences
  • 1 Applied computing → Transportation
  • 1 Computing methodologies → Concurrent algorithms
  • 1 Information systems → Clustering
  • Show More...

  • Refine by Keyword
  • 2 Approximation Algorithms
  • 1 Change detection
  • 1 Complexity of Games
  • 1 Geographically Weighted Regression
  • 1 Human mobility
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 3 2023
  • 2 2020
  • 1 2021

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