4 Search Results for "Zhang, Xianghui"

Document
DOI: 10.4230/LIPIcs.ECRTS.2025.2
Multi-Objective Memory Bandwidth Regulation and Cache Partitioning for Multicore Real-Time Systems

Authors: Binqi Sun, Zhihang Wei, Andrea Bastoni, Debayan Roy, Mirco Theile, Tomasz Kloda, Rodolfo Pellizzoni, and Marco Caccamo

Published in: LIPIcs, Volume 335, 37th Euromicro Conference on Real-Time Systems (ECRTS 2025)

Abstract
Memory bandwidth regulation and cache partitioning are widely used techniques for achieving predictable timing in real-time computing systems. Combined with partitioned scheduling, these methods require careful co-allocation of tasks and resources to cores, as task execution times strongly depend on available allocated resources. To address this challenge, this paper presents a 0-1 linear program for task-resource co-allocation, along with a multi-objective heuristic designed to minimize resource usage while guaranteeing schedulability under a preemptive EDF scheduling policy. Our heuristic employs a multi-layer framework, where an outer layer explores resource allocations using Pareto-pruned search, and an inner layer optimizes task allocation by solving a knapsack problem using dynamic programming. To evaluate the performance of the proposed optimization algorithm, we profile real-world benchmarks on an embedded AMD UltraScale+ ZCU102 platform, with fine-grained resource partitioning enabled by the Jailhouse hypervisor, leveraging cache set partitioning and MemGuard for memory bandwidth regulation. Experiments based on the benchmarking results show that the proposed 0-1 linear program outperforms existing mixed-integer programs by finding more optimal solutions within the same time limit. Moreover, the proposed multi-objective multi-layer heuristic performs consistently better than the state-of-the-art multi-resource-task co-allocation algorithm in terms of schedulability, resource usage, number of non-dominated solutions, and computational efficiency.
Cite as

Binqi Sun, Zhihang Wei, Andrea Bastoni, Debayan Roy, Mirco Theile, Tomasz Kloda, Rodolfo Pellizzoni, and Marco Caccamo. Multi-Objective Memory Bandwidth Regulation and Cache Partitioning for Multicore Real-Time Systems. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sun_et_al:LIPIcs.ECRTS.2025.2,
  author =	{Sun, Binqi and Wei, Zhihang and Bastoni, Andrea and Roy, Debayan and Theile, Mirco and Kloda, Tomasz and Pellizzoni, Rodolfo and Caccamo, Marco},
  title =	{{Multi-Objective Memory Bandwidth Regulation and Cache Partitioning for Multicore Real-Time Systems}},
  booktitle =	{37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-377-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{335},
  editor =	{Mancuso, Renato},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2025.2},
  URN =		{urn:nbn:de:0030-drops-235807},
  doi =		{10.4230/LIPIcs.ECRTS.2025.2},
  annote =	{Keywords: Multi-objective optimization, memory bandwidth regulation, cache partitioning, partitioned scheduling, real-time systems}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.9
Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model

Authors: Sharareh Alipour, Ermiya Farokhnejad, and Tobias Mömke

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We investigate semi-streaming algorithms for the Traveling Salesman Problem (TSP). Specifically, we focus on a variant known as the (1,2)-TSP, where the distances between any two vertices are either one or two. Our primary emphasis is on the closely related Maximum Path Cover Problem, which aims to find a collection of vertex-disjoint paths that covers the maximum number of edges in a graph. We propose an algorithm that, for any ε > 0, achieves a (2/3-ε)-approximation of the maximum path cover size for an n-vertex graph, using poly(1/ε) passes. This result improves upon the previous 1/2-approximation by Behnezhad et al. [Soheil Behnezhad et al., 2023] in the semi-streaming model. Building on this result, we design a semi-streaming algorithm that constructs a tour for an instance of (1,2)-TSP with an approximation factor of (4/3 + ε), improving upon the previous 3/2-approximation factor algorithm by Behnezhad et al. [Soheil Behnezhad et al., 2023]. Furthermore, we extend our approach to develop an approximation algorithm for the Maximum TSP (Max-TSP), where the goal is to find a Hamiltonian cycle with the maximum possible weight in a given weighted graph G. Our algorithm provides a (7/12 - ε)-approximation for Max-TSP in poly(1/(ε)) passes, improving on the previously known (1/2-ε)-approximation obtained via maximum weight matching in the semi-streaming model.
Cite as

Sharareh Alipour, Ermiya Farokhnejad, and Tobias Mömke. Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{alipour_et_al:LIPIcs.STACS.2025.9,
  author =	{Alipour, Sharareh and Farokhnejad, Ermiya and M\"{o}mke, Tobias},
  title =	{{Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.9},
  URN =		{urn:nbn:de:0030-drops-228342},
  doi =		{10.4230/LIPIcs.STACS.2025.9},
  annote =	{Keywords: (1,2)-TSP, Max-TSP, Maximum Path Cover, Semi-Streaming Algorithms, Approximation Algorithms, Graph Algorithms}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GIScience.2023.80
The Ups and Downs of London High Streets Throughout COVID-19 Pandemic: Insights from Footfall-Based Clustering Analysis (Short Paper)

Authors: Xinglei Wang, Xianghui Zhang, and Tao Cheng

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

Abstract
As an important part of the economic and social fabric of urban areas, high streets were hit hard during the COVID-19 pandemic, resulting in massive closures of shops and plunge of footfall. To better understand how high streets respond to and recover from the pandemic, this paper examines the performance of London’s high streets, focusing on footfall-based clustering analysis. Applying time series clustering to longitudinal footfall data derived from a mobile phone GPS dataset spanning over two years, we identify distinct groups of high streets with similar footfall change patterns. By analysing the resulting clusters' footfall dynamics, composition and geographic distribution, we uncover the diverse responses of different high streets to the pandemic disruption. Furthermore, we explore the factors driving specific footfall change patterns by examining the number of local and nonlocal visitors. This research addresses gaps in the existing literature by presenting a holistic view of high street responses throughout the pandemic and providing in-depth analysis of footfall change patterns and underlying causes. The implications and insights can inform strategies for the revitalisation and redevelopment of high streets in the post-pandemic era.
Cite as

Xinglei Wang, Xianghui Zhang, and Tao Cheng. The Ups and Downs of London High Streets Throughout COVID-19 Pandemic: Insights from Footfall-Based Clustering Analysis (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 80:1-80:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.GIScience.2023.80,
  author =	{Wang, Xinglei and Zhang, Xianghui and Cheng, Tao},
  title =	{{The Ups and Downs of London High Streets Throughout COVID-19 Pandemic: Insights from Footfall-Based Clustering Analysis}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{80:1--80: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.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.80},
  URN =		{urn:nbn:de:0030-drops-189754},
  doi =		{10.4230/LIPIcs.GIScience.2023.80},
  annote =	{Keywords: High street, performance, footfall, clustering analysis, COVID-19}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GIScience.2023.92
Unlocking the Power of Mobile Phone Application Data to Accelerate Transport Decarbonisation (Short Paper)

Authors: Xianghui Zhang and Tao Cheng

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

Abstract
Decarbonising transport is crucial in addressing climate change and achieving the Net Zero target. However, limitations arising from traditional data sources and methods obstruct the provision of individual travel information with comprehensive travel modes, high spatiotemporal granularity and updating frequency for achieving transport decarbonisation. Mobile phone application data, an essentially new form of data, can provide valuable travel information after effective mining and assist in progress monitoring, policy evaluation, and system optimisation in transport decarbonisation. This paper proposes a standardised methodology to unlock the power of mobile phone application data for supporting transport decarbonisation. Three typical cases are employed to demonstrate the capabilities of the generated individual multimodal dataset, including monitoring Londoners’ 20-minute active travel target, transport GHGs emissions and their contributors, and evaluating small-scale transport interventions. The paper also discusses the limitations of mobile phone application data, such as issues surrounding data privacy and regulation.
Cite as

Xianghui Zhang and Tao Cheng. Unlocking the Power of Mobile Phone Application Data to Accelerate Transport Decarbonisation (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 92:1-92:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{zhang_et_al:LIPIcs.GIScience.2023.92,
  author =	{Zhang, Xianghui and Cheng, Tao},
  title =	{{Unlocking the Power of Mobile Phone Application Data to Accelerate Transport Decarbonisation}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{92:1--92: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.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.92},
  URN =		{urn:nbn:de:0030-drops-189873},
  doi =		{10.4230/LIPIcs.GIScience.2023.92},
  annote =	{Keywords: Transport decarbonisation, Mobile phone application data, Application, London}
}
  • Refine by Type
  • 4 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 2 2023

  • Refine by Author
  • 2 Cheng, Tao
  • 2 Zhang, Xianghui
  • 1 Alipour, Sharareh
  • 1 Bastoni, Andrea
  • 1 Caccamo, Marco
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs

  • Refine by Classification
  • 1 Applied computing → Sociology
  • 1 Applied computing → Transportation
  • 1 Computer systems organization → Embedded software
  • 1 Computer systems organization → Real-time systems
  • 1 Information systems → Geographic information systems
  • Show More...

  • Refine by Keyword
  • 1 (1,2)-TSP
  • 1 Application
  • 1 Approximation Algorithms
  • 1 COVID-19
  • 1 Graph Algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact