35 Search Results for "Zhang, Zhen"


Document
Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means

Authors: Nicole Funk, Annika Hennes, Johanna Hillebrand, and Sarah Sturm

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)


Abstract
We study discrete k-clustering problems in general metric spaces that are constrained by a combination of two different fairness conditions within the demographic fairness model. Given a metric space (P,d), where every point in P is equipped with a protected attribute, and a number k, the goal is to partition P into k clusters with a designated center each, such that a center-based objective function is minimized and the attributes are fairly distributed with respect to the following two fairness concepts: 1) group fairness: We aim for clusters with balanced numbers of attributes by specifying lower and upper bounds for the desired attribute proportions. 2) diverse center selection: Clusters have natural representatives, i.e., their centers. We ask for a balanced set of representatives by specifying the desired number of centers to choose from each attribute. Dickerson, Esmaeili, Morgenstern, and Pena [John P. Dickerson et al., 2023] denote the combination of these two constraints as doubly constrained fair clustering. They present algorithms whose guarantees depend on the best known approximation factors for either of these problems. Currently, this implies an 8-approximation with a small additive violation on the group fairness constraint. For k-center, we improve this approximation factor to 4 with a small additive violation. This guarantee also depends on the currently best algorithm for DS-fair k-center given by Jones, Nguyen and Nguyen [Matthew Jones et al., 2020]. For k-median and k-means, we propose the first constant-factor approximation algorithms. Our algorithms transform a solution that satisfies diverse center selection into a doubly constrained fair clustering using an LP-based approach. Furthermore, our results are generalizable to other center-selection constraints, such as matroid k-clustering and knapsack constraints.

Cite as

Nicole Funk, Annika Hennes, Johanna Hillebrand, and Sarah Sturm. Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{funk_et_al:LIPIcs.SWAT.2026.19,
  author =	{Funk, Nicole and Hennes, Annika and Hillebrand, Johanna and Sturm, Sarah},
  title =	{{Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.19},
  URN =		{urn:nbn:de:0030-drops-260551},
  doi =		{10.4230/LIPIcs.SWAT.2026.19},
  annote =	{Keywords: Clustering, Fairness, Approximation Algorithms, k-center, k-median, k-means}
}
Document
Model-Agnostic Uncertainty-Aware Semantic Segmentation with Conformal Risk Guarantees for Scene Understanding

Authors: Bakary Badjie, José Cecílio, Nils-Jonathan Friedrich, Norman Seyffer, Georg Jäger, and António Casimiro

Published in: OASIcs, Volume 143, 30th Ada-Europe International Conference on Reliable Software Technologies (AEiC 2026)


Abstract
Accurate and reliable scene segmentation is a fundamental requirement for autonomous navigation systems operating in open and dynamic environments. As these systems increasingly rely on data-driven perception modules, their safety and operational robustness hinge on well-calibrated uncertainty estimates that can support explicit control of prediction errors through conformal calibration. Most existing uncertainty-aware segmentation approaches remain architecture-specific and are not evaluated under a common uncertainty-and-calibration protocol across distinct segmentation architectures and datasets. This work introduces a model-agnostic conformal segmentation pipeline that enables operationally meaningful, calibration-based error control in real-world deployments. The proposed framework treats segmentation networks as black boxes and operates on per-pixel class probabilities that are fine-tuned through evidential deep learning (EDL) to decompose aleatoric and epistemic uncertainties. We then apply pixel-wise, class-conditional split-conformal calibration to derive acceptance thresholds for user-defined target error rates. We instantiate the pipeline with DINOv2, Mask2Former, and SegFormer and evaluate it on a newly collected Lisbon street scene (LiSS) dataset; additional cross-dataset results on COCO, using a restricted set of safety-relevant classes, are reported in the appendix. Results show architecture- and class-dependent in-domain uncertainty-error alignment and indicate that dataset shift weakens uncertainty-based filtering and conformal risk control. This motivates continuous monitoring and recalibration as a practical requirement for trustworthy segmentation in safety-critical navigation.

Cite as

Bakary Badjie, José Cecílio, Nils-Jonathan Friedrich, Norman Seyffer, Georg Jäger, and António Casimiro. Model-Agnostic Uncertainty-Aware Semantic Segmentation with Conformal Risk Guarantees for Scene Understanding. In 30th Ada-Europe International Conference on Reliable Software Technologies (AEiC 2026). Open Access Series in Informatics (OASIcs), Volume 143, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{badjie_et_al:OASIcs.AEiC.2026.1,
  author =	{Badjie, Bakary and Cec{\'\i}lio, Jos\'{e} and Friedrich, Nils-Jonathan and Seyffer, Norman and J\"{a}ger, Georg and Casimiro, Ant\'{o}nio},
  title =	{{Model-Agnostic Uncertainty-Aware Semantic Segmentation with Conformal Risk Guarantees for Scene Understanding}},
  booktitle =	{30th Ada-Europe International Conference on Reliable Software Technologies (AEiC 2026)},
  pages =	{1:1--1:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-425-3},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{143},
  editor =	{Filieri, Antonio and Backeman, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AEiC.2026.1},
  URN =		{urn:nbn:de:0030-drops-259199},
  doi =		{10.4230/OASIcs.AEiC.2026.1},
  annote =	{Keywords: semantic segmentation, uncertainty quantification, evidential deep learning, conformal prediction, risk control, selective prediction}
}
Document
A Survey of Real-Time Support, Analysis, and Advancements in ROS 2

Authors: Daniel Casini, Jian-Jia Chen, Jing Li, Federico Reghenzani, and Harun Teper

Published in: LITES, Volume 11, Issue 1 (2026). Leibniz Transactions on Embedded Systems, Volume 11, Issue 1


Abstract
The Robot Operating System 2 (ROS 2) has emerged as a relevant middleware framework for robotic applications, offering modularity, distributed execution, and communication. In the last six years, ROS 2 has drawn increasing attention from the real-time systems community and industry. This survey presents a comprehensive overview of research efforts that analyze, enhance, and extend ROS 2 to support real-time execution. We first provide a detailed description of the internal scheduling mechanisms of ROS 2 and its layered architecture, including the interaction with DDS-based communication and other communication middleware. We then review key contributions from the literature, covering timing analysis for both single- and multi-threaded executors, metrics such as response time, reaction time, and data age, and different communication modes. The survey also discusses community-driven enhancements to the ROS 2 runtime, including new executor algorithm designs, real-time GPU management, and microcontroller support via micro-ROS. Furthermore, we summarize techniques for bounding DDS communication delays, message filters, and profiling tools that have been developed to support analysis and experimentation. To help systematize this growing body of work, we introduce taxonomies that classify the surveyed contributions based on different criteria. This survey aims to guide both researchers and practitioners in understanding and improving the real-time capabilities of ROS 2.

Cite as

Daniel Casini, Jian-Jia Chen, Jing Li, Federico Reghenzani, and Harun Teper. A Survey of Real-Time Support, Analysis, and Advancements in ROS 2. In LITES, Volume 11, Issue 1 (2026). Leibniz Transactions on Embedded Systems, Volume 11, Issue 1, pp. 1:1-1:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@Article{casini_et_al:LITES.11.1.1,
  author =	{Casini, Daniel and Chen, Jian-Jia and Li, Jing and Reghenzani, Federico and Teper, Harun},
  title =	{{A Survey of Real-Time Support, Analysis, and Advancements in ROS 2}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{1:1--1:37},
  ISSN =	{2199-2002},
  year =	{2026},
  volume =	{11},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.11.1.1},
  URN =		{urn:nbn:de:0030-drops-257914},
  doi =		{10.4230/LITES.11.1.1},
  annote =	{Keywords: ROS 2, middleware, real-time, timing predictability, publish-subscribe}
}
Document
Research
On the Computational Cost of Knowledge Graph Embeddings

Authors: Victor Charpenay, Mansour Zoubeirou A Mayaki, and Antoine Zimmermann

Published in: TGDK, Volume 4, Issue 1 (2026). Transactions on Graph Data and Knowledge, Volume 4, Issue 1


Abstract
Over a decade, numerous Knowledge Graph Embedding (KGE) models have been designed and evaluated on reference datasets, always with increasing performance. In this paper, we re-evaluate these models with respect to their computational efficiency during training, by estimating the computational cost of the procedure expressed in floating-point operations. We design a cost model based on analytical expressions and apply it on a collection of 20 KGE models, representative of the state-of-the-art. We show that dimensionality or parameter efficiency, used in the literature to compare models with each other, are not suitable to evaluate the true cost of models. Through fixed-budget experiments, a novel approach to evaluate KGE models based on cost estimates, we re-assess the relative performance of model families compared to the state-of-the-art. Bilinear models such as ComplEx underperform with a low computational budget while hyperbolic linear models appear to offer no particular benefit compared to simpler Euclidian models, especially the MuRE model. Neural models, such as ConvE or CompGCN, achieve reasonable performance in the literature but their high computational cost appears unnecessary when compared with other models. The trade-off between efficiency and expressivity of both linear and neural models is to be further explored.

Cite as

Victor Charpenay, Mansour Zoubeirou A Mayaki, and Antoine Zimmermann. On the Computational Cost of Knowledge Graph Embeddings. In Transactions on Graph Data and Knowledge (TGDK), Volume 4, Issue 1, pp. 1:1-1:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@Article{charpenay_et_al:TGDK.4.1.1,
  author =	{Charpenay, Victor and Zoubeirou A Mayaki, Mansour and Zimmermann, Antoine},
  title =	{{On the Computational Cost of Knowledge Graph Embeddings}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{1:1--1:30},
  ISSN =	{2942-7517},
  year =	{2026},
  volume =	{4},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.4.1.1},
  URN =		{urn:nbn:de:0030-drops-256863},
  doi =		{10.4230/TGDK.4.1.1},
  annote =	{Keywords: Knowledge Graph Embedding, Parameter Efficiency, Computational Budget, Green AI}
}
Document
Tight Loops, Smooth Streams: Responsive Congestion Control for Real-Time Video

Authors: Pantea Karimi, Sadjad Fouladi, Vibhaalakshmi Sivaraman, and Mohammad Alizadeh

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)


Abstract
Real-time video streaming relies on rate control to match video bitrate to network capacity while keeping latency low. Existing deployed video rate controllers react slowly to network changes, causing under-utilization and latency spikes. In contrast, modern delay-sensitive congestion control algorithms (CCAs) adapt on round-trip-time timescales, maintaining a tight feedback loop that achieves both high utilization and low latency. We introduce Vidaptive, a lightweight framework that enables real-time video to leverage responsive CCAs without codec changes. Vidaptive decouples encoding from transmission: it paces video frames at the CCA’s rate and injects dummy packets when the encoder output is insufficient, preserving a continuous feedback loop. An online algorithm dynamically adjusts the encoder’s target bitrate to align with CCA capacity while bounding frame latency. Implemented in Google WebRTC, Vidaptive improves both video quality and tail latency on diverse cellular traces. Compared to GCC, it delivers 1.5× higher bitrate, +40% VMAF, +1.4 dB SSIM, +1.3 dB PSNR, and reduces 95th-percentile frame latency by 57% (2.2 seconds). Against Salsify, it achieves lower tail latency without invasive codec modifications. These results show that coupling existing CCAs with a thin adaptation layer can outperform specialized video rate controllers while remaining deployable in practice.

Cite as

Pantea Karimi, Sadjad Fouladi, Vibhaalakshmi Sivaraman, and Mohammad Alizadeh. Tight Loops, Smooth Streams: Responsive Congestion Control for Real-Time Video. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 9:1-9:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{karimi_et_al:OASIcs.NINeS.2026.9,
  author =	{Karimi, Pantea and Fouladi, Sadjad and Sivaraman, Vibhaalakshmi and Alizadeh, Mohammad},
  title =	{{Tight Loops, Smooth Streams: Responsive Congestion Control for Real-Time Video}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{9:1--9:29},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.9},
  URN =		{urn:nbn:de:0030-drops-255942},
  doi =		{10.4230/OASIcs.NINeS.2026.9},
  annote =	{Keywords: real-time video, congestion control, transport protocols, video rate control, low-latency video communication, tight feedback loop}
}
Document
In-Kernel Aggregation and Broadcast Acceleration for Distributed Communication

Authors: Jianchang Su, Yifan Zhang, and Wei Zhang

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)


Abstract
Broadcasting and aggregation dominate the communication overhead in distributed systems, from machine learning training to data analytics. Current acceleration approaches require specialized hardware (RDMA) or dedicated resources (DPDK), limiting their deployment in commodity clouds. However, we present a counter-intuitive alternative: rather than bypassing the kernel, we move operations into it using eBPF. While this imposes severe constraints including no floating-point, limited memory, and stateless execution, we show these restrictions paradoxically drive innovative protocol designs that yield unexpected benefits. We introduce AggBox, which implements broadcast and aggregation operations entirely within eBPF’s constrained environment. Our key innovations include stateless group acknowledgments for reliability, edge quantization for floating-point aggregation using only integer arithmetic, and tail-call chains that create virtual memory beyond eBPF’s 512-byte stack limit. These designs emerge from and exploit the constraints rather than fighting them. AggBox achieves remarkable performance on commodity hardware: 84.5% reduction in broadcast latency, 43× speedup for MapReduce workloads, and 56.1% faster ML gradient aggregation, all without specialized NICs or dedicated cores. Beyond performance, our work demonstrates that constrained environments can drive fundamental innovation in protocol design, offering insights for future resource-limited and verified systems.

Cite as

Jianchang Su, Yifan Zhang, and Wei Zhang. In-Kernel Aggregation and Broadcast Acceleration for Distributed Communication. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{su_et_al:OASIcs.NINeS.2026.13,
  author =	{Su, Jianchang and Zhang, Yifan and Zhang, Wei},
  title =	{{In-Kernel Aggregation and Broadcast Acceleration for Distributed Communication}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{13:1--13:23},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.13},
  URN =		{urn:nbn:de:0030-drops-255981},
  doi =		{10.4230/OASIcs.NINeS.2026.13},
  annote =	{Keywords: eBPF, distributed communication, broadcast, aggregation, in-kernel processing, XDP}
}
Document
SwiftQueue: Optimizing Low-Latency Applications with Swift Packet Queuing

Authors: Siddhant Ray, Xi Jiang, Jack Luo, Nick Feamster, and Junchen Jiang

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)


Abstract
Low Latency, Low Loss, and Scalable Throughput (L4S), as an emerging router-queue management technique, has seen steady deployment in the industry. An L4S-enabled router assigns each packet to the queue based on the packet header marking. Currently, L4S employs per-flow queue selection, i.e., all packets of a flow are marked the same way and thus use the same queues, even though each packet is marked separately. However, this may hurt tail latency and latency-sensitive applications because transient congestion and queue buildups may only affect a fraction of packets in a flow. We present SwiftQueue, a new L4S queue-selection strategy in which a sender uses a novel per-packet latency predictor to pinpoint which packets likely have latency spikes or drops. The insight is that many packet-level latency variations result from complex interactions among recent packets at shared router queues. Yet, these intricate packet-level latency patterns are hard to learn efficiently by traditional models. Instead, SwiftQueue uses a custom Transformer, which is well-studied for its expressiveness on sequential patterns, to predict the next packet’s latency based on the latencies of recently received ACKs. Based on the predicted latency of each outgoing packet, SwiftQueue’s sender dynamically marks the L4S packet header to assign packets to potentially different queues, even within the same flow. Using real network traces, we show that SwiftQueue is 45-65% more accurate in predicting latency and its variations than state-of-art methods. Based on its latency prediction, SwiftQueue reduces the tail latency for L4S-enabled flows by 36-45%, compared with the existing L4S queue-selection method.

Cite as

Siddhant Ray, Xi Jiang, Jack Luo, Nick Feamster, and Junchen Jiang. SwiftQueue: Optimizing Low-Latency Applications with Swift Packet Queuing. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 24:1-24:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{ray_et_al:OASIcs.NINeS.2026.24,
  author =	{Ray, Siddhant and Jiang, Xi and Luo, Jack and Feamster, Nick and Jiang, Junchen},
  title =	{{SwiftQueue: Optimizing Low-Latency Applications with Swift Packet Queuing}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{24:1--24:29},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.24},
  URN =		{urn:nbn:de:0030-drops-256093},
  doi =		{10.4230/OASIcs.NINeS.2026.24},
  annote =	{Keywords: Latency prediction, L4S Queue Management}
}
Document
Research
Mining Inter-Document Argument Structures in Scientific Papers for an Argument Web

Authors: Florian Ruosch, Cristina Sarasua, and Abraham Bernstein

Published in: TGDK, Volume 3, Issue 3 (2025). Transactions on Graph Data and Knowledge, Volume 3, Issue 3


Abstract
In Argument Mining, predicting argumentative relations between texts (or spans) remains one of the most challenging aspects, even more so in the cross-document setting. This paper makes three key contributions to advance research in this domain. We first extend an existing dataset, the Sci-Arg corpus, by annotating it with explicit inter-document argumentative relations, thereby allowing arguments to be distributed over several documents forming an Argument Web; these new annotations are published using Semantic Web technologies (RDF, OWL). Second, we explore and evaluate three automated approaches for predicting these inter-document argumentative relations, establishing critical baselines on the new dataset. We find that a simple classifier based on discourse indicators with access to context outperforms neural methods. Third, we conduct a comparative analysis of these approaches for both intra- and inter-document settings, identifying statistically significant differences in results that indicate the necessity of distinguishing between these two scenarios. Our findings highlight significant challenges in this complex domain and open crucial avenues for future research on the Argument Web of Science, particularly for those interested in leveraging Semantic Web technologies and knowledge graphs to understand scholarly discourse. With this, we provide the first stepping stones in the form of a benchmark dataset, three baseline methods, and an initial analysis for a systematic exploration of this field relevant to the Web of Data and Science.

Cite as

Florian Ruosch, Cristina Sarasua, and Abraham Bernstein. Mining Inter-Document Argument Structures in Scientific Papers for an Argument Web. In Transactions on Graph Data and Knowledge (TGDK), Volume 3, Issue 3, pp. 4:1-4:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@Article{ruosch_et_al:TGDK.3.3.4,
  author =	{Ruosch, Florian and Sarasua, Cristina and Bernstein, Abraham},
  title =	{{Mining Inter-Document Argument Structures in Scientific Papers for an Argument Web}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{4:1--4:33},
  ISSN =	{2942-7517},
  year =	{2025},
  volume =	{3},
  number =	{3},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.3.3.4},
  URN =		{urn:nbn:de:0030-drops-252159},
  doi =		{10.4230/TGDK.3.3.4},
  annote =	{Keywords: Argument Mining, Large Language Models, Knowledge Graphs, Link Prediction}
}
Document
On the (In)Approximability of the Monitoring Edge Geodetic Set Problem

Authors: Davide Bilò, Giordano Colli, Luca Forlizzi, and Stefano Leucci

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)


Abstract
We study the minimum Monitoring Edge Geodetic Set (MEG-Set) problem introduced in [Foucaud et al., CALDAM'23]: given a graph G, we say that an edge is monitored by a pair u,v of vertices if all shortest paths between u and v traverse e; the goal is to find a subset M of vertices of G such that each edge of G is monitored by at least one pair of vertices in M, and |M| is minimized. In this paper, we prove that all polynomial-time approximation algorithms for the minimum MEG-Set problem must have an approximation ratio of Ω(log n), unless 𝖯 = NP. To the best of our knowledge, this is the first non-constant inapproximability result known for this problem. We also strengthen the known NP-hardness of the problem on 2-apex graphs by showing that the same result holds for 1-apex graphs. This leaves open the question of determining whether the problem remains NP-hard on planar (i.e., 0-apex) graphs. On the positive side, we design an algorithm that computes good approximate solutions for hereditary graph classes that admit efficiently computable balanced separators of truly sublinear size. This immediately yields polynomial-time approximation algorithms achieving an approximation ratio of O(n^{1/4} √{log n}) on planar graphs, graphs with bounded genus, and k-apex graphs with k = O(n^{1/4}). On graphs with bounded treewidth, we obtain an approximation ratio of O(log^{3/2} n). This compares favorably with the best-known approximation algorithm for general graphs, which achieves an approximation ratio of O(√{n log n}) via a simple reduction to the Set Cover problem.

Cite as

Davide Bilò, Giordano Colli, Luca Forlizzi, and Stefano Leucci. On the (In)Approximability of the Monitoring Edge Geodetic Set Problem. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ISAAC.2025.14,
  author =	{Bil\`{o}, Davide and Colli, Giordano and Forlizzi, Luca and Leucci, Stefano},
  title =	{{On the (In)Approximability of the Monitoring Edge Geodetic Set Problem}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{14:1--14:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.14},
  URN =		{urn:nbn:de:0030-drops-249226},
  doi =		{10.4230/LIPIcs.ISAAC.2025.14},
  annote =	{Keywords: Monitoring Edge Geodetic Set, Inapproximability, Approximation Algorithms}
}
Document
PhD Panel
Unsupervised Multimodal Learning for Fault Diagnosis and Prognosis - Application to Radiotherapy Systems (PhD Panel)

Authors: Kélian Poujade, Louise Travé-Massuyès, Jérémy Pirard, and Laure Vieillevigne

Published in: OASIcs, Volume 136, 36th International Conference on Principles of Diagnosis and Resilient Systems (DX 2025)


Abstract
Modern complex systems, such as radiotherapy machines, require robust strategies for fault detection, diagnosis, and prognosis to ensure operational continuity and patient safety. While data-driven methods have gained traction, few studies address diagnostic and prognostic tasks using multimodal operational data under unsupervised or semi-supervised learning settings. This gap is particularly critical given the scarcity of labeled failure data in real-world environments. This work aims to design a unified approach for fault detection, diagnosis, and prognosis using multimodal data in the absence of complete labeling. To this end, autoencoders (AEs) are employed due to their suitability for unsupervised and self-supervised learning, flexibility in handling heterogeneous data, and ability to construct latent representations optimized for various downstream tasks. A specific implementation based on a Long Short-Term Memory β-Variational Autoencoder (LSTM-β-VAE) was developed to detect anomalies in machine logs. This framework is applied to TomoTherapy® systems - a highly complex and under-explored use case within the radiotherapy domain. Initial results demonstrate strong anomaly detection performance on both a public benchmark dataset (HDFS) and a proprietary dataset derived from real-world TomoTherapy® machine faults. Beyond methodology, the paper includes a concise literature review of multimodal learning and data-driven diagnosis and prognosis with a focus on AEs. Based on this review, key research directions are identified for the continuation of the thesis, especially the integration of explainable AI as a means to enhance diagnosis capabilities in the absence of labeled faults.

Cite as

Kélian Poujade, Louise Travé-Massuyès, Jérémy Pirard, and Laure Vieillevigne. Unsupervised Multimodal Learning for Fault Diagnosis and Prognosis - Application to Radiotherapy Systems (PhD Panel). In 36th International Conference on Principles of Diagnosis and Resilient Systems (DX 2025). Open Access Series in Informatics (OASIcs), Volume 136, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{poujade_et_al:OASIcs.DX.2025.16,
  author =	{Poujade, K\'{e}lian and Trav\'{e}-Massuy\`{e}s, Louise and Pirard, J\'{e}r\'{e}my and Vieillevigne, Laure},
  title =	{{Unsupervised Multimodal Learning for Fault Diagnosis and Prognosis - Application to Radiotherapy Systems}},
  booktitle =	{36th International Conference on Principles of Diagnosis and Resilient Systems (DX 2025)},
  pages =	{16:1--16:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-394-2},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{136},
  editor =	{Quinones-Grueiro, Marcos and Biswas, Gautam and Pill, Ingo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.DX.2025.16},
  URN =		{urn:nbn:de:0030-drops-248058},
  doi =		{10.4230/OASIcs.DX.2025.16},
  annote =	{Keywords: Artificial Intelligence, Diagnosis, Prognosis, Radiotherapy machines}
}
Document
DX Competition
Data-Driven Fault Detection and Isolation Enhanced with System Structural Relationships (DX Competition)

Authors: Austin Coursey, Abel Diaz-Gonzalez, Marcos Quinones-Grueiro, and Gautam Biswas

Published in: OASIcs, Volume 136, 36th International Conference on Principles of Diagnosis and Resilient Systems (DX 2025)


Abstract
Fault detection and isolation are becoming increasingly important as modern systems become more complex. To encourage the development of new fault detection solutions that can operate with limited noisy data and an incomplete mathematical model, the DX 2025 LiU-ICE competition for diagnosis of the air path of an internal combustion engine was introduced. In this paper, we present our winning solution to this competition. Our fault detection architecture starts with a semi-supervised Transformer Autoencoder trained to reconstruct nominal data. Detected faults are then passed through a rule-based fault persistence filter that aims to suppress false positives. Once a fault is detected, we use four neural networks trained to estimate features determined from structural analysis of a partial system model. The residuals of these networks are fed to a supervised fault classification network that estimates the fault probabilities. With this architecture, we achieved an 87% detection rate with a 0% false alarm rate on the provided competition data. Additionally, our isolation architecture assigned the correct fault 73.8% probabilty on average. On unseen competition data from a new driving cycle, we achieved a 100% detection rate and assigned the correct fault 66.2% probability on average. On the other hand, the Transformer Autoencoder failed to transfer to the new driving conditions, causing many false alarms. We discuss ways future work can reduce this.

Cite as

Austin Coursey, Abel Diaz-Gonzalez, Marcos Quinones-Grueiro, and Gautam Biswas. Data-Driven Fault Detection and Isolation Enhanced with System Structural Relationships (DX Competition). In 36th International Conference on Principles of Diagnosis and Resilient Systems (DX 2025). Open Access Series in Informatics (OASIcs), Volume 136, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{coursey_et_al:OASIcs.DX.2025.15,
  author =	{Coursey, Austin and Diaz-Gonzalez, Abel and Quinones-Grueiro, Marcos and Biswas, Gautam},
  title =	{{Data-Driven Fault Detection and Isolation Enhanced with System Structural Relationships}},
  booktitle =	{36th International Conference on Principles of Diagnosis and Resilient Systems (DX 2025)},
  pages =	{15:1--15:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-394-2},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{136},
  editor =	{Quinones-Grueiro, Marcos and Biswas, Gautam and Pill, Ingo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.DX.2025.15},
  URN =		{urn:nbn:de:0030-drops-248043},
  doi =		{10.4230/OASIcs.DX.2025.15},
  annote =	{Keywords: fault detection, fault isolation, autoencoder}
}
Document
Zero-Knowledge Authenticator for Blockchain: Policy-Private and Obliviously Updateable

Authors: Kostas Kryptos Chalkias, Deepak Maram, Arnab Roy, Joy Wang, and Aayush Yadav

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)


Abstract
Transaction details and participant identities on the blockchain are often publicly exposed. In this work, we posit that blockchain’s transparency should not come at the cost of privacy. To that end, we introduce zero-knowledge authenticators (zkAt), a new cryptographic primitive for privacy-preserving authentication on public blockchains. zkAt utilizes zero-knowledge proofs to enable users to authenticate transactions, while keeping the underlying authentication policies private. Prior solutions for such policy-private authentication required the use of threshold signatures, which can only hide the threshold access structure itself. In comparison, zkAt provides privacy for arbitrarily complex authentication policies, and offers a richer interface even within the threshold access structure by, for instance, allowing for the combination of signatures under distinct signature schemes. In order to construct zkAt, we design a compiler that transforms the popular Groth16 non-interactive zero knowledge (NIZK) proof system into a NIZK with equivocable verification keys, a property that we define in this work. Then, for any zkAt constructed using proof systems with this new property, we show that all public information must be independent of the policy, thereby achieving policy-privacy. Next, we give an extension of zkAt, called zkAt^+ wherein, assuming a trusted authority, policies can be updated obliviously in the sense that a third-party learns no new information when a policy is updated by the policy issuer. We also give a theoretical construction for zkAt^+ using recursive NIZKs, and explore the integration of zkAt into modern blockchains. Finally, to evaluate their feasibility, we implement both our schemes for a specific threshold access structure. Our findings show that zkAt achieves comparable performance to traditional threshold signatures, while also attaining privacy for significantly more complex policies with very little overhead.

Cite as

Kostas Kryptos Chalkias, Deepak Maram, Arnab Roy, Joy Wang, and Aayush Yadav. Zero-Knowledge Authenticator for Blockchain: Policy-Private and Obliviously Updateable. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{kryptoschalkias_et_al:LIPIcs.AFT.2025.2,
  author =	{Kryptos Chalkias, Kostas and Maram, Deepak and Roy, Arnab and Wang, Joy and Yadav, Aayush},
  title =	{{Zero-Knowledge Authenticator for Blockchain: Policy-Private and Obliviously Updateable}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.2},
  URN =		{urn:nbn:de:0030-drops-247218},
  doi =		{10.4230/LIPIcs.AFT.2025.2},
  annote =	{Keywords: Blockchain privacy, authentication schemes, threshold wallets, zero knowledge proofs}
}
Document
Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering

Authors: Sina Bagheri Nezhad, Sayan Bandyapadhyay, and Tianzhi Chen

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)


Abstract
In a seminal work, Chierichetti et al. [Chierichetti et al., 2017] introduced the (t,k)-fair clustering problem: Given a set of red points and a set of blue points in a metric space, a clustering is called fair if the number of red points in each cluster is at most t times and at least 1/t times the number of blue points in that cluster. The goal is to compute a fair clustering with at most k clusters that optimizes certain objective function. Considering this problem, they designed a polynomial-time O(1)- and O(t)-approximation for the k-center and the k-median objective, respectively. Recently, Carta et al. [Carta et al., 2024] studied this problem with the sum-of-radii objective and obtained a (6+ε)-approximation with running time O((k log_{1+ε}(k/ε))^k n^O(1)), i.e., fixed-parameter tractable in k. Here n is the input size. In this work, we design the first polynomial-time O(1)-approximation for (t,k)-fair clustering with the sum-of-radii objective, improving the result of Carta et al. Our result places sum-of-radii in the same group of objectives as k-center, that admit polynomial-time O(1)-approximations. This result also implies a polynomial-time O(1)-approximation for the Euclidean version of the problem, for which an f(k)⋅n^O(1)-time (1+ε)-approximation was known due to Drexler et al. [Drexler et al., 2023]. Here f is an exponential function of k. We are also able to extend our result to any arbitrary 𝓁 ≥ 2 number of colors when t = 1. This matches known results for the k-center and k-median objectives in this case. The significant disparity of sum-of-radii compared to k-center and k-median presents several complex challenges, all of which we successfully overcome in our work. Our main contribution is a novel cluster-merging-based analysis technique for sum-of-radii that helps us achieve the constant-approximation bounds.

Cite as

Sina Bagheri Nezhad, Sayan Bandyapadhyay, and Tianzhi Chen. Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 62:1-62:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{bagherinezhad_et_al:LIPIcs.ESA.2025.62,
  author =	{Bagheri Nezhad, Sina and Bandyapadhyay, Sayan and Chen, Tianzhi},
  title =	{{Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{62:1--62:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.62},
  URN =		{urn:nbn:de:0030-drops-245309},
  doi =		{10.4230/LIPIcs.ESA.2025.62},
  annote =	{Keywords: fair clustering, sum-of-radii clustering, approximation algorithms}
}
Document
Toward an Earth-Independent System for EVA Mission Planning: Integrating Physical Models, Domain Knowledge, and Agentic RAG to Provide Explainable LLM-Based Decision Support

Authors: Kaisheng Li and Richard S. Whittle

Published in: OASIcs, Volume 130, Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)


Abstract
We propose a unified framework for an Earth‑independent AI system that provides explainable, context‑aware decision support for EVA mission planning by integrating six core components: a fine‑tuned EVA domain LLM, a retrieval‑augmented knowledge base, a short-term memory store, physical simulation models, an agentic orchestration layer, and a multimodal user interface. To ground our design, we analyze the current roles and substitution potential of the Mission Control Center - identifying which procedural and analytical functions can be automated onboard while preserving human oversight for experiential and strategic tasks. Building on this framework, we introduce RASAGE (Retrieval & Simulation Augmented Guidance Agent for Exploration), a proof‑of‑concept toolset that combines Microsoft Phi‑4‑mini‑instruct with a FAISS (Facebook AI Similarity Search)‑powered EVA knowledge base and custom A* path planning and hypogravity metabolic models to generate grounded, traceable EVA plans. We outline a staged validation strategy to evaluate improvements in route efficiency, metabolic prediction accuracy, anomaly response effectiveness, and crew trust under realistic communication delays. Our findings demonstrate the feasibility of replicating key Mission Control functions onboard, enhancing crew autonomy, reducing cognitive load, and improving safety for deep‑space exploration missions.

Cite as

Kaisheng Li and Richard S. Whittle. Toward an Earth-Independent System for EVA Mission Planning: Integrating Physical Models, Domain Knowledge, and Agentic RAG to Provide Explainable LLM-Based Decision Support. In Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025). Open Access Series in Informatics (OASIcs), Volume 130, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{li_et_al:OASIcs.SpaceCHI.2025.6,
  author =	{Li, Kaisheng and Whittle, Richard S.},
  title =	{{Toward an Earth-Independent System for EVA Mission Planning: Integrating Physical Models, Domain Knowledge, and Agentic RAG to Provide Explainable LLM-Based Decision Support}},
  booktitle =	{Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)},
  pages =	{6:1--6:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-384-3},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{130},
  editor =	{Bensch, Leonie and Nilsson, Tommy and Nisser, Martin and Pataranutaporn, Pat and Schmidt, Albrecht and Sumini, Valentina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SpaceCHI.2025.6},
  URN =		{urn:nbn:de:0030-drops-239967},
  doi =		{10.4230/OASIcs.SpaceCHI.2025.6},
  annote =	{Keywords: Human-AI Interaction for Space Exploration, Extravehicular Activities, Cognitive load and Human Performance Issues, Human Systems Exploration, Lunar Exploration, LLM}
}
Document
NEREUS: An Assistive Decision Support System for Real-Time, Adaptive Route Guidance in Extravehicular Navigation Activities on the Lunar Surface

Authors: Jasmine Q. Wu, Andrew J. Hwang, and Matthew J. Bietz

Published in: OASIcs, Volume 130, Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)


Abstract
Extravehicular Activity (EVA) is one of the most complex operational endeavors during human lunar exploration. A key aspect of successful operations involves adapting procedures to address unexpected hazards on the lunar surface. Current route mapping systems rely heavily on static navigation planning around craters, high elevations, and extreme weather conditions to accomplish pre-defined mission objectives. However, the high-resolution data necessary for reliable route mapping is often unavailable. To address this challenge, we have designed NEREUS, a Decision Support System (DSS) that helps EVA operators on the ground respond to anomalies faster by simulating multiple alternative routes in parallel and visualizing trade-offs in consumable resources, speed, and safety as well as impact on overall mission timeline. The system offloads computationally intensive tasks like calculating the impact of evolving hazard data, allowing operators to focus on higher-level decision-making.

Cite as

Jasmine Q. Wu, Andrew J. Hwang, and Matthew J. Bietz. NEREUS: An Assistive Decision Support System for Real-Time, Adaptive Route Guidance in Extravehicular Navigation Activities on the Lunar Surface. In Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025). Open Access Series in Informatics (OASIcs), Volume 130, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{wu_et_al:OASIcs.SpaceCHI.2025.25,
  author =	{Wu, Jasmine Q. and Hwang, Andrew J. and Bietz, Matthew J.},
  title =	{{NEREUS: An Assistive Decision Support System for Real-Time, Adaptive Route Guidance in Extravehicular Navigation Activities on the Lunar Surface}},
  booktitle =	{Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)},
  pages =	{25:1--25:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-384-3},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{130},
  editor =	{Bensch, Leonie and Nilsson, Tommy and Nisser, Martin and Pataranutaporn, Pat and Schmidt, Albrecht and Sumini, Valentina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SpaceCHI.2025.25},
  URN =		{urn:nbn:de:0030-drops-240158},
  doi =		{10.4230/OASIcs.SpaceCHI.2025.25},
  annote =	{Keywords: Human Computer Interaction (HCI), Adaptive Navigation, Decision Support, Cognitive Load Analysis, Decision Support System, Extravehicular Activity}
}
  • Refine by Type
  • 35 Document/PDF
  • 27 Document/HTML

  • Refine by Publication Year
  • 7 2026
  • 17 2025
  • 1 2024
  • 5 2023
  • 2 2022
  • Show More...

  • Refine by Author
  • 3 Feng, Qilong
  • 3 Zhang, Zhen
  • 2 Dumbrava, Stefania
  • 2 Huang, Ziyun
  • 2 Jiménez-Ruiz, Ernesto
  • Show More...

  • Refine by Series/Journal
  • 14 LIPIcs
  • 9 OASIcs
  • 4 LITES
  • 8 TGDK

  • Refine by Classification
  • 4 Information systems → Graph-based database models
  • 4 Theory of computation → Facility location and clustering
  • 3 Computing methodologies → Neural networks
  • 3 Computing methodologies → Semantic networks
  • 2 Computer systems organization → Embedded and cyber-physical systems
  • Show More...

  • Refine by Keyword
  • 3 Large Language Models
  • 2 Approximation Algorithms
  • 2 Explainable AI
  • 2 Fuzzing
  • 2 Knowledge Graphs
  • 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