24 Search Results for "Li, Hong"

Volume

LIPIcs, Volume 181

31st International Symposium on Algorithms and Computation (ISAAC 2020)

ISAAC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference)

Editors: Yixin Cao, Siu-Wing Cheng, and Minming Li

Document
DOI: 10.4230/LIPIcs.ITCS.2024.73
Dynamic Maximal Matching in Clique Networks

Authors: Minming Li, Peter Robinson, and Xianbin Zhu

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We consider the problem of computing a maximal matching with a distributed algorithm in the presence of batch-dynamic changes to the graph topology. We assume that a graph of n nodes is vertex-partitioned among k players that communicate via message passing. Our goal is to provide an efficient algorithm that quickly updates the matching even if an adversary determines batches of 𝓁 edge insertions or deletions. We first show a lower bound of Ω((𝓁 log k)/(k²log n)) rounds for recomputing a matching assuming an oblivious adversary who is unaware of the initial (random) vertex partition as well as the current state of the players, and a stronger lower bound of Ω(𝓁/(klog n)) rounds against an adaptive adversary, who may choose any balanced (but not necessarily random) vertex partition initially and who knows the current state of the players. We also present a randomized algorithm that has an initialization time of O(n/(k log n)) rounds, while achieving an update time that that is independent of n: In more detail, the update time is O(⌈𝓁/k⌉ log k) against an oblivious adversary, who must fix all updates in advance. If we consider the stronger adaptive adversary, the update time becomes O (⌈𝓁/√k⌉ log k) rounds.
Cite as

Minming Li, Peter Robinson, and Xianbin Zhu. Dynamic Maximal Matching in Clique Networks. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 73:1-73:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ITCS.2024.73,
  author =	{Li, Minming and Robinson, Peter and Zhu, Xianbin},
  title =	{{Dynamic Maximal Matching in Clique Networks}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{73:1--73:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.73},
  URN =		{urn:nbn:de:0030-drops-196017},
  doi =		{10.4230/LIPIcs.ITCS.2024.73},
  annote =	{Keywords: distributed graph algorithm, dynamic network, maximal matching, randomized algorithm, lower bound}
}
Document
Survey
DOI: 10.4230/TGDK.1.1.7
Rule Learning over Knowledge Graphs: A Review

Authors: Hong Wu, Zhe Wang, Kewen Wang, Pouya Ghiasnezhad Omran, and Jiangmeng Li

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
Compared to black-box neural networks, logic rules express explicit knowledge, can provide human-understandable explanations for reasoning processes, and have found their wide application in knowledge graphs and other downstream tasks. As extracting rules manually from large knowledge graphs is labour-intensive and often infeasible, automated rule learning has recently attracted significant interest, and a number of approaches to rule learning for knowledge graphs have been proposed. This survey aims to provide a review of approaches and a classification of state-of-the-art systems for learning first-order logic rules over knowledge graphs. A comparative analysis of various approaches to rule learning is conducted based on rule language biases, underlying methods, and evaluation metrics. The approaches we consider include inductive logic programming (ILP)-based, statistical path generalisation, and neuro-symbolic methods. Moreover, we highlight important and promising application scenarios of rule learning, such as rule-based knowledge graph completion, fact checking, and applications in other research areas.
Cite as

Hong Wu, Zhe Wang, Kewen Wang, Pouya Ghiasnezhad Omran, and Jiangmeng Li. Rule Learning over Knowledge Graphs: A Review. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{wu_et_al:TGDK.1.1.7,
  author =	{Wu, Hong and Wang, Zhe and Wang, Kewen and Omran, Pouya Ghiasnezhad and Li, Jiangmeng},
  title =	{{Rule Learning over Knowledge Graphs: A Review}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{7:1--7:23},
  ISSN =	{2942-7517},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/TGDK.1.1.7},
  URN =		{urn:nbn:de:0030-drops-194813},
  doi =		{10.4230/TGDK.1.1.7},
  annote =	{Keywords: Rule learning, Knowledge graphs, Link prediction}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.31
Enumerating Maximal Induced Subgraphs

Authors: Yixin Cao

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

Abstract
Given a graph G, the maximal induced subgraphs problem asks to enumerate all maximal induced subgraphs of G that belong to a certain hereditary graph class. While its optimization version, known as the minimum vertex deletion problem in literature, has been intensively studied, enumeration algorithms were only known for a few simple graph classes, e.g., independent sets, cliques, and forests, until very recently [Conte and Uno, STOC 2019]. There is also a connected variation of this problem, where one is concerned with only those induced subgraphs that are connected. We introduce two new approaches, which enable us to develop algorithms that solve both variations for a number of important graph classes. A general technique that has been proven very powerful in enumeration algorithms is to build a solution map, i.e., a multiple digraph on all the solutions of the problem, and the key of this approach is to make the solution map strongly connected, so that a simple traversal of the solution map solves the problem. First, we introduce retaliation-free paths to certify strong connectedness of the solution map we build. Second, generalizing the idea of Cohen, Kimelfeld, and Sagiv [JCSS 2008], we introduce an apparently very restricted version of the maximal (connected) induced subgraphs problem, and show that it is equivalent to the original problem in terms of solvability in incremental polynomial time. Moreover, we give reductions between the two variations, so that it suffices to solve one of the variations for each class we study. Our work also leads to direct and simpler proofs of several important known results.
Cite as

Yixin Cao. Enumerating Maximal Induced Subgraphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 31:1-31:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cao:LIPIcs.ESA.2023.31,
  author =	{Cao, Yixin},
  title =	{{Enumerating Maximal Induced Subgraphs}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{31:1--31:13},
  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.31},
  URN =		{urn:nbn:de:0030-drops-186841},
  doi =		{10.4230/LIPIcs.ESA.2023.31},
  annote =	{Keywords: enumeration algorithm, hereditary graph class, maximal induced subgraph}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.38
Scheduling with a Limited Testing Budget: Tight Results for the Offline and Oblivious Settings

Authors: Christoph Damerius, Peter Kling, Minming Li, Chenyang Xu, and Ruilong Zhang

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

Abstract
Scheduling with testing falls under the umbrella of the research on optimization with explorable uncertainty. In this model, each job has an upper limit on its processing time that can be decreased to a lower limit (possibly unknown) by some preliminary action (testing). Recently, [Christoph Dürr et al., 2020] has studied a setting where testing a job takes a unit time, and the goal is to minimize total completion time or makespan on a single machine. In this paper, we extend their problem to the budget setting in which each test consumes a job-specific cost, and we require that the total testing cost cannot exceed a given budget. We consider the offline variant (the lower processing time is known) and the oblivious variant (the lower processing time is unknown) and aim to minimize the total completion time or makespan on a single machine. For the total completion time objective, we show NP-hardness and derive a PTAS for the offline variant based on a novel LP rounding scheme. We give a (4+ε)-competitive algorithm for the oblivious variant based on a framework inspired by the worst-case lower-bound instance. For the makespan objective, we give an FPTAS for the offline variant and a (2+ε)-competitive algorithm for the oblivious variant. Our algorithms for the oblivious variants under both objectives run in time 𝒪(poly(n/ε)). Lastly, we show that our results are essentially optimal by providing matching lower bounds.
Cite as

Christoph Damerius, Peter Kling, Minming Li, Chenyang Xu, and Ruilong Zhang. Scheduling with a Limited Testing Budget: Tight Results for the Offline and Oblivious Settings. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{damerius_et_al:LIPIcs.ESA.2023.38,
  author =	{Damerius, Christoph and Kling, Peter and Li, Minming and Xu, Chenyang and Zhang, Ruilong},
  title =	{{Scheduling with a Limited Testing Budget: Tight Results for the Offline and Oblivious Settings}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{38:1--38:15},
  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.38},
  URN =		{urn:nbn:de:0030-drops-186915},
  doi =		{10.4230/LIPIcs.ESA.2023.38},
  annote =	{Keywords: scheduling, total completion time, makespan, LP rounding, competitive analysis, approximation algorithm, NP hardness, PTAS}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.78
Massively Parallel Algorithms for the Stochastic Block Model

Authors: Zelin Li, Pan Peng, and Xianbin Zhu

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

Abstract
Learning the community structure of a large-scale graph is a fundamental problem in machine learning, computer science and statistics. Among others, the Stochastic Block Model (SBM) serves a canonical model for community detection and clustering, and the Massively Parallel Computation (MPC) model is a mathematical abstraction of real-world parallel computing systems, which provides a powerful computational framework for handling large-scale datasets. We study the problem of exactly recovering the communities in a graph generated from the SBM in the MPC model. Specifically, given kn vertices that are partitioned into k equal-sized clusters (i.e., each has size n), a graph on these kn vertices is randomly generated such that each pair of vertices is connected with probability p if they are in the same cluster and with probability q if not, where p > q > 0. We give MPC algorithms for the SBM in the (very general) s-space MPC model, where each machine is guaranteed to have memory s = Ω(log n). Under the condition that (p-q)/√p ≥ Ω̃(k^{1/2} n^{-1/2+1/(2(r-1))}) for any integer r ∈ [3,O(log n)], our first algorithm exactly recovers all the k clusters in O(kr log_s n) rounds using Õ(m) total space, or in O(rlog_s n) rounds using Õ(km) total space. If (p-q)/√p ≥ Ω̃(k^{3/4} n^{-1/4}), our second algorithm achieves O(log_s n) rounds and Õ(m) total space complexity. Both algorithms significantly improve upon a recent result of Cohen-Addad et al. [PODC'22], who gave algorithms that only work in the sublinear space MPC model, where each machine has local memory s = O(n^δ) for some constant δ > 0, with a much stronger condition on p,q,k. Our algorithms are based on collecting the r-step neighborhood of each vertex and comparing the difference of some statistical information generated from the local neighborhoods for each pair of vertices. To implement the clustering algorithms in parallel, we present efficient approaches for implementing some basic graph operations in the s-space MPC model.
Cite as

Zelin Li, Pan Peng, and Xianbin Zhu. Massively Parallel Algorithms for the Stochastic Block Model. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 78:1-78:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ESA.2023.78,
  author =	{Li, Zelin and Peng, Pan and Zhu, Xianbin},
  title =	{{Massively Parallel Algorithms for the Stochastic Block Model}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{78:1--78: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.78},
  URN =		{urn:nbn:de:0030-drops-187313},
  doi =		{10.4230/LIPIcs.ESA.2023.78},
  annote =	{Keywords: Massively Parallel Computation, Stochastic Block Model, Graph Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.97
Improved Algorithms for Online Rent Minimization Problem Under Unit-Size Jobs

Authors: Enze Sun, Zonghan Yang, and Yuhao Zhang

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

Abstract
We consider the Online Rent Minimization problem, where online jobs with release times, deadlines, and processing times must be scheduled on machines that can be rented for a fixed length period of T. The objective is to minimize the number of machine rents. This problem generalizes the Online Machine Minimization problem where machines can be rented for an infinite period, and both problems have an asymptotically optimal competitive ratio of O(log(p_max/p_min)) for general processing times, where p_max and p_min are the maximum and minimum processing times respectively. However, for small values of p_max/p_min, a better competitive ratio can be achieved by assuming unit-size jobs. Under this assumption, Devanur et al. (2014) gave an optimal e-competitive algorithm for Online Machine Minimization, and Chen and Zhang (2022) gave a (3e+7) ≈ 15.16-competitive algorithm for Online Rent Minimization. In this paper, we significantly improve the competitive ratio of the Online Rent Minimization problem under unit size to 6, by using a clean oracle-based online algorithm framework.
Cite as

Enze Sun, Zonghan Yang, and Yuhao Zhang. Improved Algorithms for Online Rent Minimization Problem Under Unit-Size Jobs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 97:1-97:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{sun_et_al:LIPIcs.ESA.2023.97,
  author =	{Sun, Enze and Yang, Zonghan and Zhang, Yuhao},
  title =	{{Improved Algorithms for Online Rent Minimization Problem Under Unit-Size Jobs}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{97:1--97:14},
  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.97},
  URN =		{urn:nbn:de:0030-drops-187500},
  doi =		{10.4230/LIPIcs.ESA.2023.97},
  annote =	{Keywords: Online Algorithm, Scheduling, Machine Minimization, Rent Minimization}
}
Document
DOI: 10.4230/LIPIcs.CPM.2023.14
MUL-Tree Pruning for Consistency and Compatibility

Authors: Christopher Hampson, Daniel J. Harvey, Costas S. Iliopoulos, Jesper Jansson, Zara Lim, and Wing-Kin Sung

Published in: LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)

Abstract
A multi-labelled tree (or MUL-tree) is a rooted tree leaf-labelled by a set of labels, where each label may appear more than once in the tree. We consider the MUL-tree Set Pruning for Consistency problem (MULSETPC), which takes as input a set of MUL-trees and asks whether there exists a perfect pruning of each MUL-tree that results in a consistent set of single-labelled trees. MULSETPC was proven to be NP-complete by Gascon et al. when the MUL-trees are binary, each leaf label is used at most three times, and the number of MUL-trees is unbounded. To determine the computational complexity of the problem when the number of MUL-trees is constant was left as an open problem. Here, we resolve this question by proving a much stronger result, namely that MULSETPC is NP-complete even when there are only two MUL-trees, every leaf label is used at most twice, and every MUL-tree is either binary or has constant height. Furthermore, we introduce an extension of MULSETPC that we call MULSETPComp, which replaces the notion of consistency with compatibility, and prove that MULSETPComp is NP-complete even when there are only two MUL-trees, every leaf label is used at most thrice, and every MUL-tree has constant height. Finally, we present a polynomial-time algorithm for instances of MULSETPC with a constant number of binary MUL-trees, in the special case where every leaf label occurs exactly once in at least one MUL-tree.
Cite as

Christopher Hampson, Daniel J. Harvey, Costas S. Iliopoulos, Jesper Jansson, Zara Lim, and Wing-Kin Sung. MUL-Tree Pruning for Consistency and Compatibility. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hampson_et_al:LIPIcs.CPM.2023.14,
  author =	{Hampson, Christopher and Harvey, Daniel J. and Iliopoulos, Costas S. and Jansson, Jesper and Lim, Zara and Sung, Wing-Kin},
  title =	{{MUL-Tree Pruning for Consistency and Compatibility}},
  booktitle =	{34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-276-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{259},
  editor =	{Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.14},
  URN =		{urn:nbn:de:0030-drops-179682},
  doi =		{10.4230/LIPIcs.CPM.2023.14},
  annote =	{Keywords: multi-labelled tree, phylogenetic tree, consistent, compatible, pruning, algorithm, NP-complete}
}
Document
DOI: 10.4230/DagRep.12.1.1
Mobility Data Science (Dagstuhl Seminar 22021)

Authors: Mohamed Mokbel, Mahmoud Sakr, Li Xiong, Andreas Züfle, Jussara Almeida, Taylor Anderson, Walid Aref, Gennady Andrienko, Natalia Andrienko, Yang Cao, Sanjay Chawla, Reynold Cheng, Panos Chrysanthis, Xiqi Fei, Gabriel Ghinita, Anita Graser, Dimitrios Gunopulos, Christian Jensen, Joon-Sook Kim, Kyoung-Sook Kim, Peer Kröger, John Krumm, Johannes Lauer, Amr Magdy, Mario Nascimento, Siva Ravada, Matthias Renz, Dimitris Sacharidis, Cyrus Shahabi, Flora Salim, Mohamed Sarwat, Maxime Schoemans, Bettina Speckmann, Egemen Tanin, Yannis Theodoridis, Kristian Torp, Goce Trajcevski, Marc van Kreveld, Carola Wenk, Martin Werner, Raymond Wong, Song Wu, Jianqiu Xu, Moustafa Youssef, Demetris Zeinalipour, Mengxuan Zhang, and Esteban Zimányi

Published in: Dagstuhl Reports, Volume 12, Issue 1 (2022)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22021 "Mobility Data Science". This seminar was held January 9-14, 2022, including 47 participants from industry and academia. The goal of this Dagstuhl Seminar was to create a new research community of mobility data science in which the whole is greater than the sum of its parts by bringing together established leaders as well as promising young researchers from all fields related to mobility data science. Specifically, this report summarizes the main results of the seminar by (1) defining Mobility Data Science as a research domain, (2) by sketching its agenda in the coming years, and by (3) building a mobility data science community. (1) Mobility data science is defined as spatiotemporal data that additionally captures the behavior of moving entities (human, vehicle, animal, etc.). To understand, explain, and predict behavior, we note that a strong collaboration with research in behavioral and social sciences is needed. (2) Future research directions for mobility data science described in this report include a) mobility data acquisition and privacy, b) mobility data management and analysis, and c) applications of mobility data science. (3) We identify opportunities towards building a mobility data science community, towards collaborations between academic and industry, and towards a mobility data science curriculum.
Cite as

Mohamed Mokbel, Mahmoud Sakr, Li Xiong, Andreas Züfle, Jussara Almeida, Taylor Anderson, Walid Aref, Gennady Andrienko, Natalia Andrienko, Yang Cao, Sanjay Chawla, Reynold Cheng, Panos Chrysanthis, Xiqi Fei, Gabriel Ghinita, Anita Graser, Dimitrios Gunopulos, Christian Jensen, Joon-Sook Kim, Kyoung-Sook Kim, Peer Kröger, John Krumm, Johannes Lauer, Amr Magdy, Mario Nascimento, Siva Ravada, Matthias Renz, Dimitris Sacharidis, Cyrus Shahabi, Flora Salim, Mohamed Sarwat, Maxime Schoemans, Bettina Speckmann, Egemen Tanin, Yannis Theodoridis, Kristian Torp, Goce Trajcevski, Marc van Kreveld, Carola Wenk, Martin Werner, Raymond Wong, Song Wu, Jianqiu Xu, Moustafa Youssef, Demetris Zeinalipour, Mengxuan Zhang, and Esteban Zimányi. Mobility Data Science (Dagstuhl Seminar 22021). In Dagstuhl Reports, Volume 12, Issue 1, pp. 1-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{mokbel_et_al:DagRep.12.1.1,
  author =	{Mokbel, Mohamed and Sakr, Mahmoud and Xiong, Li and Z\"{u}fle, Andreas and Almeida, Jussara and Anderson, Taylor and Aref, Walid and Andrienko, Gennady and Andrienko, Natalia and Cao, Yang and Chawla, Sanjay and Cheng, Reynold and Chrysanthis, Panos and Fei, Xiqi and Ghinita, Gabriel and Graser, Anita and Gunopulos, Dimitrios and Jensen, Christian and Kim, Joon-Sook and Kim, Kyoung-Sook and Kr\"{o}ger, Peer and Krumm, John and Lauer, Johannes and Magdy, Amr and Nascimento, Mario and Ravada, Siva and Renz, Matthias and Sacharidis, Dimitris and Shahabi, Cyrus and Salim, Flora and Sarwat, Mohamed and Schoemans, Maxime and Speckmann, Bettina and Tanin, Egemen and Theodoridis, Yannis and Torp, Kristian and Trajcevski, Goce and van Kreveld, Marc and Wenk, Carola and Werner, Martin and Wong, Raymond and Wu, Song and Xu, Jianqiu and Youssef, Moustafa and Zeinalipour, Demetris and Zhang, Mengxuan and Zim\'{a}nyi, Esteban},
  title =	{{Mobility Data Science (Dagstuhl Seminar 22021)}},
  pages =	{1--34},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{1},
  editor =	{Mokbel, Mohamed and Sakr, Mahmoud and Xiong, Li and Z\"{u}fle, Andreas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.1.1},
  URN =		{urn:nbn:de:0030-drops-169190},
  doi =		{10.4230/DagRep.12.1.1},
  annote =	{Keywords: Spatio-temporal, Tracking, Privacy, Behavior, Data cleaning, Data management, Analytics}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ISAAC.2020
LIPIcs, Volume 181, ISAAC 2020, Complete Volume

Authors: Yixin Cao, Siu-Wing Cheng, and Minming Li

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
LIPIcs, Volume 181, ISAAC 2020, Complete Volume
Cite as

31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 1-1012, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{cao_et_al:LIPIcs.ISAAC.2020,
  title =	{{LIPIcs, Volume 181, ISAAC 2020, Complete Volume}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{1--1012},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020},
  URN =		{urn:nbn:de:0030-drops-133439},
  doi =		{10.4230/LIPIcs.ISAAC.2020},
  annote =	{Keywords: LIPIcs, Volume 181, ISAAC 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ISAAC.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Yixin Cao, Siu-Wing Cheng, and Minming Li

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.ISAAC.2020.0,
  author =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.0},
  URN =		{urn:nbn:de:0030-drops-133448},
  doi =		{10.4230/LIPIcs.ISAAC.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ISAAC.2020.2
Worst-Case Optimal Join Algorithms (Invited Talk)

Authors: Ke Yi

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Join is the most important operator in relational databases, and remains the most expensive one despite years of research and engineering efforts. Following the ground-breaking work of Atserias, Grohe, and Marx in 2008, worst-case optimal join algorithms have been discovered, which has led to not only a series of beautiful theoretical results, but also new database systems based on drastically different query evaluation techniques. In this talk, I will present an overview of this topic, including algorithms in various computation models (sequential and parallel), variants of the problem (full, Boolean, and counting), and approximate solutions.
Cite as

Ke Yi. Worst-Case Optimal Join Algorithms (Invited Talk). In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{yi:LIPIcs.ISAAC.2020.2,
  author =	{Yi, Ke},
  title =	{{Worst-Case Optimal Join Algorithms}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.2},
  URN =		{urn:nbn:de:0030-drops-133462},
  doi =		{10.4230/LIPIcs.ISAAC.2020.2},
  annote =	{Keywords: query evaluation}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.37
Learning and Testing Variable Partitions

Authors: Andrej Bogdanov and Baoxiang Wang

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
Let F be a multivariate function from a product set Σ^n to an Abelian group G. A k-partition of F with cost δ is a partition of the set of variables V into k non-empty subsets (X_1, ̇s, X_k) such that F(V) is δ-close to F_1(X_1)+ ̇s+F_k(X_k) for some F_1, ̇s, F_k with respect to a given error metric. We study algorithms for agnostically learning k partitions and testing k-partitionability over various groups and error metrics given query access to F. In particular we show that 1) Given a function that has a k-partition of cost δ, a partition of cost O(k n^2)(δ + ε) can be learned in time Õ(n^2 poly 1/ε) for any ε > 0. In contrast, for k = 2 and n = 3 learning a partition of cost δ + ε is NP-hard. 2) When F is real-valued and the error metric is the 2-norm, a 2-partition of cost √(δ^2 + ε) can be learned in time Õ(n^5/ε^2). 3) When F is Z_q-valued and the error metric is Hamming weight, k-partitionability is testable with one-sided error and O(kn^3/ε) non-adaptive queries. We also show that even two-sided testers require Ω(n) queries when k = 2. This work was motivated by reinforcement learning control tasks in which the set of control variables can be partitioned. The partitioning reduces the task into multiple lower-dimensional ones that are relatively easier to learn. Our second algorithm empirically increases the scores attained over previous heuristic partitioning methods applied in this context.
Cite as

Andrej Bogdanov and Baoxiang Wang. Learning and Testing Variable Partitions. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 37:1-37:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bogdanov_et_al:LIPIcs.ITCS.2020.37,
  author =	{Bogdanov, Andrej and Wang, Baoxiang},
  title =	{{Learning and Testing Variable Partitions}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{37:1--37:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.37},
  URN =		{urn:nbn:de:0030-drops-117221},
  doi =		{10.4230/LIPIcs.ITCS.2020.37},
  annote =	{Keywords: partitioning, agnostic learning, property testing, sublinear-time algorithms, hypergraph cut, reinforcement learning}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2019.16
Scheduling Self-Suspending Tasks: New and Old Results

Authors: Jian-Jia Chen, Tobias Hahn, Ruben Hoeksma, Nicole Megow, and Georg von der Brüggen

Published in: LIPIcs, Volume 133, 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)

Abstract
In computing systems, a job may suspend itself (before it finishes its execution) when it has to wait for certain results from other (usually external) activities. For real-time systems, such self-suspension behavior has been shown to induce performance degradation. Hence, the researchers in the real-time systems community have devoted themselves to the design and analysis of scheduling algorithms that can alleviate the performance penalty due to self-suspension behavior. As self-suspension and delegation of parts of a job to non-bottleneck resources is pretty natural in many applications, researchers in the operations research (OR) community have also explored scheduling algorithms for systems with such suspension behavior, called the master-slave problem in the OR community. This paper first reviews the results for the master-slave problem in the OR literature and explains their impact on several long-standing problems for scheduling self-suspending real-time tasks. For frame-based periodic real-time tasks, in which the periods of all tasks are identical and all jobs related to one frame are released synchronously, we explore different approximation metrics with respect to resource augmentation factors under different scenarios for both uniprocessor and multiprocessor systems, and demonstrate that different approximation metrics can create different levels of difficulty for the approximation. Our experimental results show that such more carefully designed schedules can significantly outperform the state-of-the-art.
Cite as

Jian-Jia Chen, Tobias Hahn, Ruben Hoeksma, Nicole Megow, and Georg von der Brüggen. Scheduling Self-Suspending Tasks: New and Old Results. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ECRTS.2019.16,
  author =	{Chen, Jian-Jia and Hahn, Tobias and Hoeksma, Ruben and Megow, Nicole and von der Br\"{u}ggen, Georg},
  title =	{{Scheduling Self-Suspending Tasks: New and Old Results}},
  booktitle =	{31st Euromicro Conference on Real-Time Systems (ECRTS 2019)},
  pages =	{16:1--16:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-110-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{133},
  editor =	{Quinton, Sophie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2019.16},
  URN =		{urn:nbn:de:0030-drops-107532},
  doi =		{10.4230/LIPIcs.ECRTS.2019.16},
  annote =	{Keywords: Self-suspension, master-slave problem, computational complexity, speedup factors}
}
Document
DOI: 10.4230/OASIcs.ASD.2019.2
Feasibility Study and Benchmarking of Embedded MPC for Vehicle Platoons

Authors: Iñaki Martín Soroa, Amr Ibrahim, Dip Goswami, and Hong Li

Published in: OASIcs, Volume 68, Workshop on Autonomous Systems Design (ASD 2019)

Abstract
This paper performs a feasibility analysis of deploying Model Predictive Control (MPC) for vehicle platooning on an On-Board Unit (OBU) and performance benchmarking considering interference from other (system) tasks running on an OBU. MPC is a control strategy that solves an implicit (on-line) or explicit (off-line) optimisation problem for computing the control input in every sample. OBUs have limited computational resources. The challenge is to implement an MPC algorithm on such automotive Electronic Control Units (ECUs) with an acceptable timing behavior. Moreover, we should be able to stop the execution if necessary at the cost of performance. We measured the computational capability of a unit developed by Cohda Wireless and NXP under the influence of its Operating System (OS). Next, we analysed the computational requirements of different state-of-the-art MPC algorithms by estimating their execution times. We use off-the-shelf and free automatic code generators for MPC to run a number of relevant MPC algorithms on the platform. From the results, we conclude that it is feasible to implement MPC on automotive ECUs for vehicle platooning and we further benchmark their performance in terms of MPC parameters such as prediction horizon and system dimension.
Cite as

Iñaki Martín Soroa, Amr Ibrahim, Dip Goswami, and Hong Li. Feasibility Study and Benchmarking of Embedded MPC for Vehicle Platoons. In Workshop on Autonomous Systems Design (ASD 2019). Open Access Series in Informatics (OASIcs), Volume 68, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{martinsoroa_et_al:OASIcs.ASD.2019.2,
  author =	{Mart{\'\i}n Soroa, I\~{n}aki and Ibrahim, Amr and Goswami, Dip and Li, Hong},
  title =	{{Feasibility Study and Benchmarking of Embedded MPC for Vehicle Platoons}},
  booktitle =	{Workshop on Autonomous Systems Design (ASD 2019)},
  pages =	{2:1--2:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-102-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{68},
  editor =	{Saidi, Selma and Ernst, Rolf and Ziegenbein, Dirk},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ASD.2019.2},
  URN =		{urn:nbn:de:0030-drops-103359},
  doi =		{10.4230/OASIcs.ASD.2019.2},
  annote =	{Keywords: Model predictive control, vehicle platoon, embedded implementation, code generation}
}
  • Refine by Author
  • 4 Li, Minming
  • 3 Cao, Yixin
  • 2 Cheng, Siu-Wing
  • 2 Jansson, Jesper
  • 2 Li, Qian
  • Show More...

  • Refine by Classification
  • 2 Information systems → Data management systems
  • 2 Mathematics of computing
  • 2 Theory of computation
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Applied computing → Command and control
  • Show More...

  • Refine by Keyword
  • 1 Analytics
  • 1 Art Gallery Problem
  • 1 Behavior
  • 1 Conference Organization
  • 1 Data cleaning
  • Show More...

  • Refine by Type
  • 23 document
  • 1 volume

  • Refine by Publication Year
  • 8 2016
  • 6 2023
  • 5 2020
  • 2 2019
  • 1 2018
  • 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