Schloss Dagstuhl – Leibniz Center for Informatics
DROPS Dagstuhl Research Online Publication ServerNot a member yet
23028 research outputs found
Sort by
Improved Approximation Algorithms for Three-Dimensional Knapsack
Full text linkWe study the three-dimensional Knapsack (3DK) problem, in which we are given a set of axis-aligned cuboids with associated profits and an axis-aligned cube knapsack. The objective is to find a non-overlapping axis-aligned packing (by translation) of the maximum profit subset of cuboids into the cube. The previous best approximation algorithm is due to Diedrich, Harren, Jansen, Thöle, and Thomas (2008), who gave a (7+ε)-approximation algorithm for 3DK and a (5+ε)-approximation algorithm for the variant when the items can be rotated by 90 degrees around any axis, for any constant ε > 0. Chlebík and Chlebíková (2009) showed that the problem does not admit an asymptotic polynomial-time approximation scheme.
We provide an improved polynomial-time (139/29+ε) ≈ 4.794-approximation algorithm for 3DK and (30/7+ε) ≈ 4.286-approximation when rotations by 90 degrees are allowed. We also provide improved approximation algorithms for several variants such as the cardinality case (when all items have the same profit) and uniform profit-density case (when the profit of an item is equal to its volume). Our key technical contribution is container packing - a structured packing in 3D such that all items are assigned into a constant number of containers, and each container is packed using a specific strategy based on its type. We first show the existence of highly profitable container packings. Thereafter, we show that one can find near-optimal container packing efficiently using a variant of the Generalized Assignment Problem (GAP)
Persistent (Co)Homology in Matrix Multiplication Time
Full text linkMost algorithms for computing persistent homology do so by tracking cycles that represent homology classes. There are many choices of such cycles, and specific choices have found different uses in applications. Although it is known that persistence diagrams can be computed in matrix multiplication time for the more general case of zigzag persistent homology [Milosavljević et al., 2011], it is not clear how to extract cycle representatives, especially if specific representatives are desired. In this paper, we provide the same matrix multiplication bound for computing representatives for the two choices common in applications in the case of ordinary persistent (co)homology. We first provide a fast version of the reduction algorithm, which is simpler than the algorithm in [Milosavljević et al., 2011], but returns a different set of representatives than the standard algorithm [Edelsbrunner et al., 2002]. We then give a fast version of a variant called the row algorithm [De Silva et al., 2011], which returns the same representatives as the standard algorithm
Incremental Algorithm and Local Search for Minimum Non-Obtuse Triangulations (CG Challenge)
No full textIn this year’s CG challenge, the task was to compute a non-obtuse triangulation of given planar regions while minimizing the number of Steiner points. Our team (Gwamegi) used two approaches. The first approach incrementally adds Steiner points on the grid defined by the input points in the planar regions, while maintaining a Delaunay triangulation. The second approach is an iterated local search, which runs insertion and deletion steps alternatingly. In the insertion step, we add a new Steiner point inside a maximal convex subpolygon in the current triangulation. In the deletion step, we remove a number of Steiner points packed in a small region. We use both our approaches to obtain non-obtuse triangulations for all 150 instances. We use our second approach to reduce the number of Steiner points from the non-obtuse triangulations. We have successfully computed non-obtuse triangulations using a sufficiently small number of Steiner points for all instances
LIPIcs, Volume 333, ECOOP 2025, Complete Volume
No full textLIPIcs, Volume 333, ECOOP 2025, Complete Volum
GSOHC: Global Synchronization Optimization in Heterogeneous Computing
Full text linkThe use of heterogeneous systems has become widespread and popular in the past decade with more than one type of processor, such as CPUs, GPUs (Graphics Processing Units), and FPGAs (Field Programmable Gate Arrays) etc. A wide range of applications use both CPU and GPU to leverage the benefits of their unique features and strengths. Therefore, collaborative computation between CPU and GPU is essential to achieve high program performance. However, poorly placed global synchronization barriers and synchronous memory transfers are the main bottlenecks to enhanced program performance, preventing CPU and GPU computations from overlapping.
Based on this observation, we propose a new optimization technique called hetero-sync motion that can relocate such barrier instructions to new locations, resulting in improved performance in CPU-GPU heterogeneous programs. Further, we propose GSOHC, a compiler analysis and optimization framework that automatically finds opportunities for hetero-sync motion in the input program and then performs code transformation to apply the optimization. Our static analysis is a context-sensitive, flow-sensitive inter-procedural data-flow analysis with three phases to identify the optimization opportunities precisely. We have implemented GSOHC using LLVM/Clang infrastructure. On A4000, P100 and A100 GPUs, our optimization achieves speedups of up to 1.8x, 1.9x and 1.9x over the baseline, respectively
Chain of Grounded Objectives: Concise Goal-Oriented Prompting for Code Generation
Full text linkThe use of Large Language Models (LLMs) for code generation has gained significant attention in recent years. Existing methods often aim to improve the quality of generated code by incorporating additional contextual information or guidance into input prompts. Many of these approaches adopt process-oriented reasoning strategies, mimicking human-like step-by-step thinking; however, they may not always align with the structured nature of programming languages. This paper introduces Chain of Grounded Objectives (CGO), a concise goal-oriented prompting approach that embeds functional objectives into prompts to enhance code generation. By focusing on precisely defined objectives rather than explicit procedural steps, CGO aligns more naturally with programming tasks while retaining flexibility. Empirical evaluations on HumanEval, MBPP, their extended versions, and LiveCodeBench show that CGO achieves accuracy comparable to or better than existing methods while using fewer tokens, making it a more efficient approach to LLM-based code generation
Scaling Up: Revisiting Mining Android Sandboxes at Scale for Malware Classification (Replication Paper)
No full textThe widespread use of smartphones in daily life has raised concerns about privacy and security among researchers and practitioners. Privacy issues are generally highly prevalent in mobile applications, particularly targeting the Android platform - the most popular mobile operating system. For this reason, several techniques have been proposed to identify malicious behavior in Android applications, including the Mining Android Sandbox approach (MAS approach), which aims to identify malicious behavior in repackaged Android applications (apps). However, previous empirical studies evaluated the MAS approach using a small dataset consisting of only 102 pairs of original and repackaged apps. This limitation raises questions about the external validity of their findings and whether the MAS approach can be generalized to larger datasets. To address these concerns, this paper presents the results of a replication study focused on evaluating the performance of the MAS approach regarding its capabilities of correctly classifying malware from different families. Unlike previous studies, our research employs a dataset that is an order of magnitude larger, comprising 4,076 pairs of apps covering a more diverse range of Android malware families. Surprisingly, our findings indicate a poor performance of the MAS approach for identifying malware, with the F1-score decreasing from 0.90 for the small dataset used in the previous studies to 0.54 in our more extensive dataset. Upon closer examination, we discovered that certain malware families partially account for the low accuracy of the MAS approach, which fails to classify a repackaged version of an app as malware correctly. Our findings highlight the limitations of the MAS approach, particularly when scaled, and underscore the importance of complementing it with other techniques to detect a broader range of malware effectively. This opens avenues for further discussion on addressing the blind spots that affect the accuracy of the MAS approach
Reusing Caches and Invariants for Efficient and Sound Incremental Static Analysis (Artifact)
Full text linkStatic analysis by means of abstract interpretation is a tool of choice for proving absence of some classes of errors, typically undefined behaviors in code, in a sound way. However, static analysis tools are hardly integrated in CI/CD processes. One of the main reasons is that they are still time- and memory-expensive to apply after every single patch when developing a program. For solving this issue, incremental static analysis helps developers quickly obtain analysis results after making changes to a program. However, existing approaches are often not guaranteed to be sound, limited to specific analyses, or tied to specific tools. This limits their generalizability and applicability in practice, especially for large and critical software. In this paper, we propose a generic, sound approach to incremental static analysis that is applicable to any abstract interpreter. Our approach leverages the similarity between two versions of a program to soundly reuse previously computed analysis results. We introduce novel methods for summarizing functions and reusing loop invariants. They significantly reduce the cost of reanalysis, while maintaining soundness and a high level of precision. We have formalized our approach, proved it sound, implemented it in Eva, the abstract interpreter of Frama-C, and evaluated it on a set of real-world commits of open-source programs
Quantifying Cache Side-Channel Leakage by Refining Set-Based Abstractions (Artifact)
Full text linkThis is the accompanying artifact for the ECOOP 25' paper "Quantifying Cache Side-Channel Leakage by Refining Set-Based Abstractions"