Peter Damaschke

TCS Journal 2025 Journal Article

On central placements of new vertices in a planar point set

• Peter Damaschke
• Fredrik Ekstedt
• Raad Salman

The vertices of an edge-weighted clique shall be placed in the plane so as to minimize the sum of all weighted distances, called the spread. Driven by practical applications in factory layout planning, we consider this problem under several constraints. First we show, in the Manhattan metric, the NP-completeness of the version where some vertices are already placed, and some minimum distance is prescribed between any two vertices. However, we can optimally append one new vertex to n placed vertices in O ( n 2 ) time. For the problem without minimum distance requirements but with many unplaced vertices, we give some structural properties of optimal solutions.

SoCS Conference 2020 Conference Paper

Branch-and-Bound for the Precedence Constrained Generalized Traveling Salesman Problem

• Raad Salman
• Fredrik Ekstedt
• Peter Damaschke

The Precedence Constrained Generalized Traveling Salesman Problem (PCGTSP) combines the Generalized Traveling Salesman Problem (GTSP) and the Sequential Ordering Problem (SOP). We present a novel branching technique for the GTSP which enables the extension of a powerful pruning technique. This is combined with some modifications of known bounding methods for related problems. The algorithm manages to solve problem instances with 12-26 groups within a minute, and instances with around 50 groups which are denser with precedence constraints within 24 hours.

TCS Journal 2019 Journal Article

Combinatorial search in two and more rounds

• Peter Damaschke

In a combinatorial search problem we wish to identify an unknown element by binary tests, where the edges of a hypergraph specify the available tests. We show that, for rather general cases of this problem, the worst-case minimum number of tests, even if adaptive testing is permitted, can already be achieved in a small number of rounds of parallel tests. In particular, the maximum number of necessary rounds grows only as the square root of the number of elements, and two rounds are enough if, e. g. , the test number is close to the number of elements, or the hypergraph is a graph. We also provide polynomial-time, hardness, and parameterized results on the computational complexity of finding optimal strategies for some cases, including graphs and tree hypergraphs.

MFCS Conference 2017 Conference Paper

Dividing Splittable Goods Evenly and With Limited Fragmentation

• Peter Damaschke

A splittable good provided in n pieces shall be divided as evenly as possible among m agents, where every agent can take shares of at most F pieces. We call F the fragmentation. For F=1 we can solve the max-min and min-max problems in linear time. The case F=2 has neat formulations and structural characterizations in terms of weighted graphs. Here we focus on perfectly balanced solutions. While the problem is strongly NP-hard in general, it can be solved in linear time if m>=n-1, and a solution always exists in this case. Moreover, case F=2 is fixed-parameter tractable in the parameter 2m-n. The results also give rise to various open problems.

TCS Journal 2016 Journal Article

Deterministic versus randomized adaptive test cover

• Peter Damaschke

In a combinatorial search problem with binary tests, we are given a set of elements (vertices) and a hypergraph of possible tests (hyperedges), and the goal is to find an unknown target element using a minimum number of tests. We explore the expected test number of randomized strategies. Our main results are that the ratio of the randomized and deterministic test numbers can be logarithmic in the number of elements, that the optimal deterministic test number can be approximated (in polynomial time) only within a logarithmic factor, whereas an approximation ratio 2 can be achieved in the randomized case, and that optimal randomized strategies can be efficiently constructed at least for special classes of graphs.

TCS Journal 2015 Journal Article

Finding and enumerating large intersections

• Peter Damaschke

We study the calculation of the largest pairwise intersections in a given set family. We give combinatorial and algorithmic results both for the worst case and for set families where the frequencies of elements follow a power law, as words in texts typically do. The results can be used in faster preprocessing routines in a simple approach to multi-document summarization.

TCS Journal 2013 Journal Article

Sparse solutions of sparse linear systems: Fixed-parameter tractability and an application of complex group testing

• Peter Damaschke

A vector with at most k nonzeros is called k -sparse. We show that enumerating the support vectors of k -sparse solutions to a system A x = b of r -sparse linear equations (i. e. , where the rows of A are r -sparse) is fixed-parameter tractable (FPT) in the combined parameter r, k. We give different branching algorithms based on the close relationship to the hitting set problem in fixed-rank hypergraphs. For r = 2 the problem is simple. For 0, 1 -matrices A we can also compute an O ( r k r ) kernel. For systems of linear inequalities we get an FPT result in the combined parameter d, k, where d is the total number of minimal solutions. This is achieved by interpreting the problem as a case of group testing in the complex model. The problems stem from the reconstruction of chemical mixtures by observable reaction products.

TCS Journal 2012 Journal Article

Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover

• Peter Damaschke
• Leonid Molokov

We study a novel generalization of the Vertex Cover problem which is motivated by, e. g. , error correction (data cleaning) prior to inference of chemical mixtures by their observable reaction products. We focus on the important case of deciding on one of two candidate substances. This problem has nice graph-theoretic formulations situated between Vertex Cover and 3-Hitting Set. In order to characterize its parameterized complexity we devise parameter-preserving reductions, and we show that some minimum solution can be computed faster than by solving 3-Hitting Set in general. More explicitly, we introduce the Union Editing problem: In a hypergraph with red and blue vertices, edit the colors so that the red set becomes exactly the union of some hyperedges. The case of degree 2 is equivalent to Star Editing: in a graph with red and blue edges, edit the colors so that the red set becomes exactly the union of some stars, i. e. , vertices with all their incident edges. Our time bound is O ∗ ( 1. 8 4 c ) where c denotes the total number of recolored edges.

JMLR Journal 2006 Journal Article

Linear Programs for Hypotheses Selection in Probabilistic Inference Models

• Anders Bergkvist
• Peter Damaschke
• Marcel Lüthi

We consider an optimization problem in probabilistic inference: Given n hypotheses H j, m possible observations O k, their conditional probabilities p kj, and a particular O k, select a possibly small subset of hypotheses excluding the true target only with some error probability ε. After specifying the optimization goal we show that this problem can be solved through a linear program in mn variables that indicate the probabilities to discard a hypothesis given an observation. Moreover, we can compute optimal strategies where only O(m+n) of these variables get fractional values. The manageable size of the linear programs and the mostly deterministic shape of optimal strategies makes the method practicable. We interpret the dual variables as worst-case distributions of hypotheses, and we point out some counterintuitive nonmonotonic behaviour of the variables as a function of the error bound ε. One of the open problems is the existence of a purely combinatorial algorithm that is faster than generic linear programming. [abs] [ pdf ][ bib ] &copy JMLR 2006. ( edit, beta )

TCS Journal 2006 Journal Article

Parameterized enumeration, transversals, and imperfect phylogeny reconstruction

• Peter Damaschke

We study parameterized enumeration problems where we are interested in all solutions of limited size rather than just some solution of minimum cardinality. (Actually, we have to enumerate the inclusion-minimal solutions in order to get fixed-parameter tractable (FPT) results.) Two novel concepts are the notion of a full kernel that contains all small solutions and implicit enumeration of solutions in form of compressed descriptions. In particular, we study combinatorial and computational bounds for the transversal hypergraph (vertex covers in graphs is a special case), restricted to hyperedges with at most k elements. As an example, we apply the results and further special-purpose techniques to almost-perfect phylogeny reconstruction, a problem in computational biology.

TCS Journal 2005 Journal Article

On queuing lengths in on-line switching

• Peter Damaschke
• Zhen Zhou

Queues that temporarily store fixed-length packets are ubiquitous in network switches. Scheduling algorithms that prevent packet-loss are always desirable. LONGEST-QUEUE-FIRST (LQF) is an on-line greedy algorithm widely exploited because of its simplicity and efficiency. In this paper, we give improved bounds on the competitive ratio of LQF in terms of the worst-case queuing length, parameterized with respect to the optimal queuing length of a clairvoyant adversary. This gives a better picture of LQF's performance under heavy traffic than the usual (unparameterized) competitive ratio. We also discuss randomization, and we conclude with some intriguing open problems regarding a two-dimensional generalization of the problem.

TCS Journal 2003 Journal Article

Nearly optimal strategies for special cases of on-line capital investment

• Peter Damaschke

Suppose that some job must be done for a period of unspecified duration. The market offers a selection of devices that can do this job, each characterized by purchase and running costs. Which of them should we buy at what times, in order to minimize the total costs? As usual in competitive analysis, the cost of an on-line solution is compared to the optimum costs paid by a clearvoyant buyer. This problem which generalizes the basic rent-to-buy problem has been introduced by Azar et al. In the so-called convex case where lower running costs always imply higher prices, a strategy with competitive ratio 4+2 2 ≈6. 83 has been proposed. Here we consider two natural subcases of the convex case in a continuous-time model where new devices can be bought at any time. For the static case where all devices are available at the beginning, we give a simple 4-competitive deterministic algorithm, and we show that 3. 618 is a lower bound. (This is also the first non-trivial lower bound for the convex case, both for discrete and continuous time.) Furthermore, we give a 2. 88-competitive randomized algorithm. In the case that all devices have equal prices but are not all available at the beginning, we show that a very simple algorithm is 2-competitive, and we derive a 1. 618 lower bound.

TCS Journal 2002 Journal Article

Online strategies for backups

• Peter Damaschke

We consider strategies for backups from the viewpoint of competitive analysis of online problems. We concentrate upon the realistic case that faults are rare, i. e. the cost of work between two faults is typically large compared to the cost of one backup. Instead of the (worst-case) competitive ratio we use a refined and more expressive quality measure, in terms of the average fault frequency. The interesting matter is, roughly speaking, to adapt the backup frequency to the fault frequency, while future faults are unpredictable. We give an asymptotically optimal deterministic strategy and propose a randomized strategy whose expected cost beats the deterministic bound.

TCS Journal 2002 Journal Article

Two short notes on the on-line travelling salesman: handling times and lookahead

• Peter Damaschke

We study extensions of the on-line travelling salesman problem. Our results are: The optimal competitive ratio 2 for arbitrary metric spaces also holds in the case of nonzero handling times. The optimal competitive ratio 3/2 on the half-line cannot be improved by randomization, but there is a 4/3-competitive algorithm under the assumption that the server is notified when the last request has been released. This ratio is also optimal.

STOC Conference 1998 Conference Paper

Adaptive versus Nonadaptive Attribute-Efficient Learning

• Peter Damaschke

TCS Journal 1997 Journal Article

An optimal parallel algorithm for digital curve segmentation

• Peter Damaschke

First we give an optimal EREW PRAM algorithm that finds an unknown discrete monotone function ƒ, with domain and range of size n, in O(log n) time using O(n) independent threshold queries of kind “ƒ(x) ⩾ y? ”. Here “independent” means that simultaneous queries always refer to mutually disjoint values x and y. This is used for solving, within the same resources, a certain segmentation problem for words over semigroups. The classical problem of partitioning a digital curve into a minimum number of digital line segments, which is of interest in digital image processsing, turns out to be a special case of this, and can therefore be solved in O(log n) time using O(n) work on an EREW PRAM. This strengthens and generalizes all known algorithmic results about digital curve segmentation. As a further prerequisite we use the Dorst-Smeulders parametrization of digital line segments.