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.

In patrolling problems, robots (or other vehicles) must perpetually visit certain points without exceeding given individual waiting times. Some obvious applications are monitoring, maintenance, and periodic fetching of resources. We propose a new generic formulation of the problem. As its main advantage, it enables a reduction of the multi-robot case to the one-robot case in a certain graph/hypergraph pair, which also relates the problem to some classic path problems in graphs: NP-hardness is shown by a reduction from the Hamiltonian cycle problem, and on the positive side, the formulation allows solution heuristics using distances in the mentioned graph. We demonstrate this approach for the case of two robots patrolling on a line, a problem whose complexity status is open, apart from approximation results. Specifically, we solve all instances with up to 6 equidistant points, and we find some surprising effects, e.g., critical problem instances (which are feasible instances that become infeasible when any waiting time is diminished) may contain rather large individual waiting times.

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.

Abstract A splittable good provided innpieces shall be divided as evenly as possible amongmagents, where every agent can take shares from at mostFpieces. We callFthe fragmentation and mainly restrict attention to the cases $$F=1$$ F=1 and $$F=2$$ F=2 . For $$F=1$$ F=1 , the max–min and min–max problems are solvable in linear time. The case $$F=2$$ F=2 has neat formulations and structural characterizations in terms of weighted graphs. First we focus on perfectly balanced solutions. While the problem is strongly NP-hard in general, it can be solved in linear time if $$m\ge n-1$$ m≥n-1 , and a solution always exists in this case, in contrast to $$F=1$$ F=1 . Moreover, the problem is fixed-parameter tractable in the parameter $$2m-n$$ 2m-n . (Note that this parameter measures the number of agents above the trivial threshold $$m=n/2$$ m=n/2 .) The structural results suggest another related problem where unsplittable items shall be assigned to subsets so as to balance the average sizes (rather than the total sizes) in these subsets. We give an approximation-preserving reduction from our original splitting problem with fragmentation $$F=2$$ F=2 to this averaging problem, and some approximation results in cases whenmis close to eithernorn / 2.

Suppose that n elements shall be sorted by comparisons, but some subset of at most k pairs systematically returns false comparison results. This subset is unknown, but the number k is known in advance. Using a connection to feedback arc sets in tournaments (FAST), we characterize the solution space of sorting with recurring comparison faults by a FAST enumeration, which represents all information about the order that can be obtained by doing all $\left (\begin {array}{c}n\\2\end {array}\right )$ comparisons. Some optimal parameterized enumeration algorithm for FAST also works for the more general chordal graphs, and this fact contributes to the efficiency of our representation. Next we compute the solution space more efficiently, by fault-tolerant versions of Treesort and Quicksort. We need $O(n\log n +kn+k^{2}\log n)$ comparisons and $O(n\log n +kn+k^{2}\log n +kF(k^{2},k))$ time, where F(n, k) is any parameterized time bound for finding a FAST with at most k arcs. Thus, for rare faults the complexity is close to optimal. We also propose directions of further research, revolving around decision diagrams for sorting with recurring faults.

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.

Suppose that we have (i) a graph with an unknown edge set and (ii) access to an oracle that returns all neighbors of a probed vertex. We want to find the hubs, that is, vertices with degree above a given threshold. An almost obvious two-stage randomized strategy is to query randomly sampled vertices and then their neighbors. We prove that this strategy achieves, in certain classes of sparse graphs, an asymptotically optimal query number among all possible querying strategies, including adaptive strategies. A detail of importance for an optimal constant factor is the number of probes in the neighborhood of a hub candidate. We show that 2 is in general the best choice in the graphs of interest. In a similar way we analyze, in the same model, the problem of finding small, almost dominating sets. The problems and graph classes are motivated mainly by the elucidation of interaction networks in molecular biology. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(4), 344-350 2011

We consider an optimization problem in probabilistic inference: Given n hypotheses Hj, m possible observations Ok, their conditional probabilities pkj, and a particular Ok, 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.

We study the complexity of learning arbitrary Boolean functions of n variables by membership queries, provided that at most r variables are relevant, where r is fiecl and previously known.Problems of this type have important applications in fault searching, e.g.logical circuit testing and general-