102 results
Now showing1 - 10 of 102
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Iterative phase retrieval in macromolecular crystal diffraction using the gradients of intensities(International Union of Crystallography (IUCr), 2026-10-17); ; ; Iterative phase retrieval (IPR) offers a model-independent route to crystallographic structure determination but is fundamentally limited by the sampling of the diffraction pattern at Bragg positions. Consequently, conventional IPR methods typically rely on a high solvent fraction (>70%) to sufficiently constrain the solution, a condition met by only a small fraction of protein crystals. This work investigates a magnitude-and-gradient IPR algorithm that overcomes this undersampling barrier by exploiting the local intensity gradients ∇Iq observable in the diffraction patterns of finite crystals. By incorporating the gradients of the molecular transform alongside Bragg intensities, the phase problem is converted from an underdetermined system of equations to one that is overdetermined by a factor of two. Tests on simulated diffraction data for proteins in space group P1 demonstrate that the algorithm successfully reconstructs electron densities across a wide range of solvent fractions, including densely packed crystals where standard algorithms fail. Furthermore, the approach proves robust under experimentally relevant conditions, tolerating significant Poissonian noise and the loss of low-resolution terms due to a beamstop when coupled with approximate real-space support constraints. These results indicate that leveraging the fine structure of Bragg peaks at coherent X-ray sources can significantly extend the applicability of ab initio phasing.Publicationtype: Journal Article9 6 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , A 9/4-approximation for directed feedback vertex sets in quasi-transitive digraphs(2026-07); We provide the first non-trivial approximation algorithm for the fundamental directed feedback vertex set (DFVS) problem in the class of quasi-transitive digraphs. This class of digraphs encompasses both dense and sparse classes of digraphs, for which specialized DFVS algorithms were proposed in the literature, like tournaments or transitive orientations of bounded treewidth graphs. Our approximation algorithm can handle both dense graphs, as well as sparse graphs, by a single approach, which is based on carefully analysing the solutions to a linear programming relaxation of DFVS. It also handles the node-weighted DFVS problem, for which it computes a 9/4-approximation in polynomial time. Along the way, we improve and simplify the best-known deterministic polynomial-time approximation algorithms for DFVS in tournaments (Cai et al., SICOMP 2001; Mnich et al., ESA 2016).Publicationtype: Contribution to Conference84 12 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Optimization of modal reflection parameters of PCB connector and common-mode choke using Gaussian process regression and segmentation(Institute of Electrical and Electronics Engineers, 2026); ; ; ; In this contribution the electrical properties of a high-speed signal transition from a connector onto a printed circuit board (PCB) followed by a common-mode choke (CMC) in a surface mount package in terms of its modal, i.e., differentialand common-mode, reflection parameters has been investigated. An implementation of segmentation, i.e. domain decomposition and subsequent composition of subdomains, in combination with Gaussian process regression (GPR) to optimize the reflections of the PCB connectors and CMC integration on the board is presented and analyzed. GPR is used with Bayesian optimization to find an optimal set of design parameters for a 3D electromagnetic model developed in a full-wave electromagnetic field solver up to 20 GHz. The results indicate that an engineeringinformed domain decomposition strategy can reduce the computational burden of GPR-based optimization by lowering the per-evaluation full-wave cost. This surrogate-based optimization approach reduces the number of required full-wave simulations, enabling more efficient use of computational resources.Publicationtype: Conference Paper75 50 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , A survey on graph problems parameterized above and below guaranteed valuesAbstract: We survey the field of algorithms and complexity for graph problems parameterized above or below guaranteed values. Those problems seek, for a given graph G, a solution whose value is at least g(G)+k or at most g(G)−k, where g(G) is a guarantee on the value that any solution on G takes. The goal is to design algorithms which find such solution in time whose complexity in k is decoupled from that in the guarantee, or to rule out the existence of such algorithms by means of intractability results. We discuss a large number of algorithms and intractability results, and complement them by several open problems.Publicationtype: Review Article45 31 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Approximate minimum tree cover in all symmetric monotone norms simultaneously(Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2025-02-24); ; ; We study the problem of partitioning a set of n objects in a metric space into k clusters V1,...,Vk. The quality of the clustering is measured by considering the vector of cluster costs and then minimizing some monotone symmetric norm of that vector (in particular, this includes the ℓp-norms). For the costs of the clusters we take the weight of a minimum-weight spanning tree on the objects in Vi, which may serve as a proxy for the cost of traversing all objects in the cluster, for example in the context of Multirobot Coverage as studied by Zheng, Koenig, Kempe, Jain (IROS 2005), but also as a shape-invariant measure of cluster density similar to Single-Linkage Clustering. This problem has been studied by Even, Garg, Könemann, Ravi, Sinha (Oper. Res. Lett., 2004) for the setting of minimizing the weight of the largest cluster (i.e., using ℓ∞) as Min-Max Tree Cover, for which they gave a constant-factor approximation algorithm. We provide a careful adaptation of their algorithm to compute solutions which are approximately optimal with respect to all monotone symmetric norms simultaneously, and show how to find them in polynomial time. In fact, our algorithm is purely combinatorial and can process metric spaces with 10,000 points in less than a second. As an extension, we also consider the case where instead of a target number of clusters we are provided with a set of depots in the space such that every cluster should contain at least one such depot. One can consider these as the fixed starting points of some agents that will traverse all points of a cluster. For this setting also we are able to give a polynomial-time algorithm computing a constant-factor approximation with respect to all monotone symmetric norms simultaneously. To show that the algorithmic results are tight up to the precise constant of approximation attainable, we also prove that such clustering problems are already APX-hard when considering only one single ℓp norm for the objective.Publicationtype: Conference Paper54 26 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , A quasi-polynomial time algorithm for multi-arrival on tree-like multigraphs(Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2025-02-24); ; Propp machines, or rotor-router models, are a classic tool to simulate random systems in forms of Markov chains by deterministic systems. To this end, the nodes of the Markov chain are replaced by switching nodes, which maintain a queue over their outgoing arcs, and a particle sent through the system traverses the top arc of the queue which is then moved to the end of the queue and the particle arrives at the next node. A key question to answer about such systems is whether a single particle can reach a particular target node, given as input an initial configuration of the queues at all switching nodes. This question was introduced by Dohrau et al. (2017) under the name of Arrival. A major open question is whether Arrival can be solved in polynomial time, as it is known to lie in NP ∩co-NP; yet the fastest known algorithm for general instances takes subexponential time (Gärtner et al., ICALP 2021). We consider a generalized version of Arrival introduced by Auger et al. (RP 2023), which requires routing multiple (potentially exponentially many) particles through a rotor graph. The Multi-Arrival problem is to determine the particle configuration that results from moving all particles from a given initial configuration to sinks. Auger et al. showed that for path-like rotor graphs with a certain uniform rotor order, the problem can be solved in polynomial time. Our main result is a quasi-polynomial-time algorithm for Multi-Arrival on tree-like rotor graphs for arbitrary rotor orders. Tree-like rotor graphs are directed multigraphs which can be obtained from undirected trees by replacing each edge by an arbitrary number of arcs in either or both directions. For trees of bounded contracted height, such as paths, the algorithm runs in polynomial time and thereby generalizes the result by Auger et al.. Moreover, we give a polynomial-time algorithm for Multi-Arrival on tree-like rotor graphs without parallel arcs.Publicationtype: Conference Paper61 30 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Space-efficient parameterized algorithms on graphs of low shrubdepthDynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms which achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n-vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels, - Independent Set can be solved in time 2O(dk) ·nO(1) using O(dk2logn) space; and - Max Cut can be solved in time nO(dk) using O(dklogn) space; and - Dominating Set can be solved in time 2O(dk) · nO(1) using nO(1) space via a randomized algorithm. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial.Publicationtype: Journal Article73 28 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Serial batching to minimize the weighted number of tardy jobsThe 1|s-batch(∞),rj|∑wjUj scheduling problem takes as input a batch setup time Δ and a set of n jobs, each having a processing time, a release date, a weight, and a due date; the task is to find a sequence of batches that minimizes the weighted number of tardy jobs. This problem was introduced by Hochbaum and Landy (Oper Res Lett 16(2):79–86, 1994); as a wide generalization of Knapsack, it is NP-hard. In this work, we provide a multivariate complexity analysis of the 1|s-batch(∞),rj|∑wjUj problem with respect to several natural parameters. That is, we establish a classification into fixed-parameter tractable and W[1]-hard problems, for parameter combinations of (i) #p = number of distinct processing times, (ii) #w = number of distinct weights, (iii) #d = number of distinct due dates, (iv) #r = number of distinct release dates. Thereby, we significantly extend the work of Hermelin et al. (Ann Oper Res 298:271–287, 2018) who analyzed the parameterized complexity of the non-batch variant of this problem without release dates. As one of our key results, we prove that 1|s-batch(∞),rj|∑wjUj is W[1]-hard parameterized by the number of distinct processing times and distinct due dates. To the best of our knowledge, these are the first parameterized intractability results for scheduling problems with few distinct processing times. Further, we show that 1|s-batch(∞),rj|∑wjUj is fixed-parameter tractable parameterized by #d+#p+#r, and parameterized by #d+#w if there is just a single release date. Both results hold even if the number of jobs per batch is limited by some integer b.Publicationtype: Journal Article51 25 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates(Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2024-09); ; We study the fundamental scheduling problem 1 | rj | P wjUj: schedule a set of n jobs with weights, processing times, release dates, and due dates on a single machine, such that each job starts after its release date and we maximize the weighted number of jobs that complete execution before their due date. Problem 1 | rj | P wjUj generalizes both Knapsack and Partition, and the simplified setting without release dates was studied by Hermelin et al. [Annals of Operations Research, 2021] from a parameterized complexity viewpoint. Our main contribution is a thorough complexity analysis of 1 | rj | P wjUj in terms of four key problem parameters: the number p# of processing times, the number w# of weights, the number d# of due dates, and the number r# of release dates of the jobs. 1 | rj | P wjUj is known to be weakly para-NP-hard even if w# + d# + r# is constant, and Heeger and Hermelin [ESA, 2024] recently showed (weak) W[1]-hardness parameterized by p# or w# even if r# is constant. Algorithmically, we show that 1 | rj | P wjUj is fixed-parameter tractable parameterized by p# combined with any two of the remaining three parameters w#, d#, and r#. We further provide pseudo-polynomial XP-time algorithms for parameter r# and d#. To complement these algorithms, we show that 1 | rj | P wjUj is (strongly) W[1]-hard when parameterized by d# + r# even if w# is constant. Our results provide a nearly complete picture of the complexity of 1 | rj | P wjUj for p#, w#, d#, and r# as parameters, and extend those of Hermelin et al. [Annals of Operations Research, 2021] for the problem 1 || P wjUj without release dates. © Matthias Kaul, Matthias Mnich, and Hendrik Molter.Publicationtype: Conference Paper45 49 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , A (3/2 + 1/e)-Approximation algorithm for ordered TSP(Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2024-08-28); ; We present a new (3/2+1/e)-approximation algorithm for the Ordered Traveling Salesperson Problem (Ordered TSP). Ordered TSP is a variant of the classic metric Traveling Salesperson Problem (TSP) where a specified subset of vertices needs to appear on the output Hamiltonian cycle in a given order, and the task is to compute a cheapest such cycle. Our approximation guarantee of approximately 1.868 holds with respect to the value of a natural new linear programming (LP) relaxation for Ordered TSP. Our result significantly improves upon the previously best known guarantee of 5/2 for this problem and thereby considerably reduces the gap between approximability of Ordered TSP and metric TSP. Our algorithm is based on a decomposition of the LP solution into weighted trees that serve as building blocks in our tour construction.Publicationtype: Conference Paper63 156