This paper studies a scheduling problem with machine calibrations for multi-interval jobs. More exactly, there are n (possibly weighted) jobs of unit size that must be scheduled on a single initially uncalibrated machine. The machine can process jobs only when calibrated, and such a calibration lasts for T time slots. The standard model by Bender et al. [Bender MA, Bunde DP, Leung VJ, McCauley S, Phillips CA (2013) Efficient scheduling to minimize calibrations. Blelloch GE, Vöcking B, eds. 25th ACM Sympos. Parallelism Algorithms Architectures SPAA ‘13 (ACM, New York), 280–287] assumes that each job has a release time and deadline between which it must be processed. We study a generalization in which each job must be processed during one of possibly many job-dependent time intervals. We consider two objectives: In the minimization version, our goal is to minimize the number of calibrations while scheduling all jobs. In the maximization version, our goal is to maximize the total weight of scheduled jobs while using at most B calibrations. For the minimization version, we present a logarithmic approximation algorithm. We also prove that the problem is set-cover hard, implying that our algorithm is optimal up to a constant factor unless P = NP. The special case when each job may be scheduled in at most two time slots is shown to be vertex-cover hard, implying that there is no [Formula: see text]-approximation algorithm based on the unique game conjecture. For the maximization version, we give an algorithm with approximation ratio [Formula: see text]. This improves upon the previously best-known algorithm, which has an approximation ratio of 1/3 [Chau V, Feng S, Li M, Wang Y, Zhang G, Zhang Y (2019) Weighted throughput maximization with calibrations. Friggstad Z, Sack JR, Salavatipour MR, eds. Algorithms Data Structures 16th Internat. Sympos. WADS 2019 Proc., Lecture Notes in Computer Science, vol. 11646 (Springer, New York), 311–324]. Moreover, we also prove that our bound on the approximation ratio is tight. Although all hardness results mentioned above hold for any [Formula: see text], we provide optimal polynomial-time algorithms for T = 2 in both the minimization version and the maximization version. Finally, we show that our methods can be extended into the m identical machines case by losing some running time, whereas all algorithmic results remain the same in both versions. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2023.0430 .

Gregor Geigle, Florian Schneider, Carolin Holtermann, Chris Biemann, Radu Timofte, Anne Lauscher, Goran Glavaš. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

Even with various regulations in place across countries and social media platforms (Government of India, 2021; European Parliament and Council of the European Union, 2022), digital abusive speech remains a significant issue. One potential approach to address this challenge is automatic text detoxification, a text style transfer (TST) approach that transforms toxic language into a more neutral or non-toxic form. To date, the availability of parallel corpora for the text detoxification task (Logacheva et al., 2022; Atwell et al., 2022; Dementieva et al., 2024a) has proven to be crucial for state-of-the-art approaches. With this work, we extend parallel text detoxification corpus to new languages—German, Chinese, Arabic, Hindi, and Amharic—testing in the extensive multilingual setup TST baselines. Next, we conduct the first of its kind an automated, explainable analysis of the descriptive features of both toxic and non-toxic sentences, diving deeply into the nuances, similarities, and differences of toxicity and detoxification across 9 languages. Finally, based on the obtained insights, we experiment with a novel text detoxification method inspired by the Chain-of-Thoughts reasoning approach, enhancing the prompting process through clustering on relevant descriptive attributes.

In this system demonstration paper, we describe the Whiteboards extension for an existing web-based platform for digital qualitative discourse analysis. Whiteboards comprise interactive graph-based interfaces to organize and manipulate objects, which can be qualitative research data, such as documents, images, etc., and analyses of these research data, such as annotations, tags, and code structures. The proposed extension offers a customizable view of the material and a wide range of actions that enable new ways of interacting and working with such resources. We show that the visualizations facilitate various use cases of qualitative data analysis, including reflection of the research process through sampling maps, creation of actor networks, and refining code taxonomies.

Modern mission-critical systems (MCS) are increasingly softwarized and interconnected. As a result, their complexity increased, and so their vulnerability against cyber-attacks. The current adoption of virtualization and service-oriented architectures (SOA) in MCSs provides additional flexibility that can be leveraged to withstand and mitigate attacks, e.g., by moving critical services or data flows. This enables the deployment of strategies for moving target defense (MTD), which allows stripping attackers of their asymmetric advantage from the long reconnaissance of MCSs. However, it is challenging to design MTD strategies, given the diverse threat landscape, resource limitations, and potential degradation in service availability. In this paper, we combine two optimization models to explore feasible service configurations for SOA-based systems and to derive subsequent MTD actions with their time schedule based on an attacker-defender game. Our results indicate that even for challenging and diverse attack scenarios, our models can defend the system by up to 90% of the system operation time with a limited MTD defender budget.

For Ontology Alignment (OA), the task is to align semantically equivalent concepts and relations from different ontologies. This task plays a crucial role in many downstream tasks and applications in academia and industry. Since manually aligning ontologies is inefficient and costly, numerous approaches exist to do this automatically. However, most approaches are tailored to specific domains, are rule-based systems or based on feature engineering, and require external knowledge. The most recent advances in the field of OA rely on the widely proven effectiveness of pre-trained language models to represent the human-generated language that describes the entities in an ontology. However, these approaches additionally require sophisticated algorithms or Graph Neural Networks to exploit an ontology’s graphical structure to achieve state-of-the-art performance. In this work, we present NLFOA, or Natural Language Focused Ontology Alignment, which purely focuses on the natural language contained in ontologies to process the ontology’s semantics as well as graphical structure. An evaluation of our approach on common OA datasets shows superior results when finetuning with only a small number of training samples. Additionally, it demonstrates strong results in a zero-shot setting which could be employed in an active learning setup to reduce human labor when manually aligning ontologies significantly.

MOTIF (MultimOdal ConTextualized Images For Language Learners) is a multimodal dataset that consists of 1125 comprehension texts retrieved from Wikipedia Simple Corpus. Allowing multimodal processing or enriching the context with multimodal information has proven imperative for many learning tasks, specifically for second language (L2) learning. In this respect, several traditional NLP approaches can assist L2 readers in text comprehension processes, such as simplifying text or giving dictionary descriptions for complex words. As nicely stated in the well-known proverb, sometimes “a picture is worth a thousand words” and an image can successfully complement the verbal message by enriching the representation, like in Pictionary books. This multimodal support can also assist on-the-fly text reading experience by providing a multimodal tool that chooses and displays the most relevant images for the difficult words, given the text context. This study mainly focuses on one of the key components to achieving this goal; collecting a multimodal dataset enriched with complex word annotation and validated image match.

In this work, we present the Golden Retriever, a system leveraging state-of-the-art visio-linguistic models (VLMs) for real-time text-image retrieval. The unique feature of our system is that it can focus on words contained in the textual query, i.e., locate and high-light them within retrieved images. An efficient two-stage process implements real-time capability and the ability to focus. Therefore, we first drastically reduce the number of images processed by a VLM. Then, in the second stage, we rank the images and highlight the focussed word using the outputs of a VLM. Further, we introduce a new and efficient algorithm based on the idea of TF-IDF to retrieve images for short textual queries. One of multiple use cases where we employ the Golden Retriever is a language learner scenario, where visual cues for "difficult" words within sentences are provided to improve a user's reading comprehension. However, since the backend is completely decoupled from the frontend, the system can be integrated into any other application where images must be retrieved fast. We demonstrate the Golden Retriever with screenshots of a minimalistic user interface.

Consider a set P of points in the unit square U = [1,0), one of them being the origin. For each point p ∈ P you may draw an axis-aligned rectangle in U with its lower-left corner being p. What is the maximum area such rectangles can cover without overlapping each other? Freedman posed this problem in 1969, asking whether one can always cover at least 50% of U. Over 40 years later, Dumitrescu and Tóth [Adrian Dumitrescu and Csaba D. Tóth, 2015] achieved the first constant coverage of 9.1%; since then, no significant progress was made. While 9.1% might seem low, the authors could not find any instance where their algorithm covers less than 50%, nourishing the hope to eventually prove a 50% bound. While we indeed significantly raise the algorithm’s coverage to 39%, we extinguish the hope of reaching 50% by giving points for which its coverage stays below 43.3%. Our analysis studies the algorithm’s average and worst-case density of so-called tiles, which represent the staircase polygons in which a point can freely choose its maximum-area rectangle. Our approach is comparatively general and may potentially help in analyzing related algorithms.