Search

This paper presents heuristics which are based on a tour splitting of a general routing tour for solving the general capacitated routing problem (GCRP). This problem is a generalization of the vehicle routing problem (VRP) and the capacitated arc routing problem (CARP).

This paper presents heuristics which are based on a tour splitting of a general routing tour for solving the general capacitated routing problem (GCRP). This problem is a generalization of the vehicle routing problem (VRP) and the capacitated arc routing problem (CARP).

Given a set of weighted directed paths in a bidirected tree, the maximum weight edge-disjoint paths problem (MWEDP) is to select a subset of the given paths such that the selected paths are edge-disjoint and the total weight of the selected paths is maximized. MWEDP is NP - hard for bidirected trees of unbounded degree, even if all weights are the same (the unweighted case). Three different approximation algorithms are implemented: a known combinatorial (5/3 + ε)-approximation algorithm A 1 for the unweighted case, a new combinatorial 2-approximation algorithm A 2 for the weighted case, and a known (5/3 + ε)-approximation algorithm A 3 for the weighted case that is based on linear programming. For algorithm A 1 , it is shown how efficient data structures can be used to obtain a worst-case running-time of O(m + n + 4 1/ε √n ċ m) for instances consisting of m paths in a tree with n nodes. Experimental results regarding the running-times and the quality of the solutions obtained by the three approximation algorithms are reported. Where possible, the approximate solutions are compared to the optimal solutions, which were computed by running CPLEX on an integer linear programming formulation of MWEDP.

In all-optical networks with wavelength-division multiplexing several connections can share a physical link if the signals are transmitted on different wavelengths. As the number of available wavelengths is limited in practice, it is important to find wavelength assignments minimizing the number of different wavelengths used. This path coloring problem is NP-hard, and the best known polynomial-time approximation algorithm for directed tree networks achieves approximation ratio 5/3, which is optimal in the class of greedy algorithms for this problem. It is shown how the algorithm can be modified in order to improve its running-time to O(Tec(N,L)) for sets of paths with maximum load L in trees with N nodes, where Tec(n, k) is the time for edge-coloring a k-regular bipartite graph with n nodes. An implementation of this efficient version of the algorithm in C++ using the LEDA class library is described, and experimental results regarding the running-times and the number of wavelengths used are reported. An additional heuristic that reduces the number of wavelengths used in the average case while maintaining the worst-case bound of 5L/3 is described.

We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is either forbidden or permitted, and we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms for the non-rotational scenario with approximation ratios 9 + ϵ and 8 + ϵ, as well as an algorithm with approximation ratio 7 + ϵ that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Furthermore, we show how the used techniques can be adapted to the case where rotation by 90° either around the z-axis or around all axes is permitted, where we obtain algorithms with approximation ratios 6 + ϵ and 5 + ϵ, respectively. Finally our methods yield a 3D generalization of a packability criterion and a strip packing algorithm with absolute approximation ratio 29/4, improving the previously best known result of 45/4.

In this paper we deal with the d-PRECOLORING EXTENSION (d-PREXT) problem in various classes of graphs. The d-PREXT problem is the special case of PRECOLORING EXTENSION problem where, for a fixed constant d, input instances are restricted to contain atmost d precolored vertices for every available color. The goal is to decide if there exists an extension of given precoloring using only available colors or to find it.We present a linear time algorithm for both, the decision and the search version of d-PREXT, in the following cases: (i) restricted to the class of k-degenerate graphs (hence also planar graphs) and with sufficiently large set S of available colors, and (ii) restrictedto the class of partial k-trees (without any size restriction on S).We also study the following problem related to d-PREXT: given an instance of the d-PREXT problem which is extendable by colors of S, what is the minimum number of colors of S sufficient to usefor precolorless vertices over all such extensions? We establish lower and upper bounds on this value for k-degenerate graphs and its various subclasses (e.g., planar graphs, outerplanar graphs) and prove tight results for the class of trees.

In this paper we analyze the computational complexity of the min-max degree triangulation problem. The problem arises in the generation of two-dimensional meshes for plane objects. We show that the problem to triangulate a plane geometric graph with degree at most seven is NP-complete.

A general technique for converting approximation algorithms for the vertex coloring problem in a class of graphs into approximation algorithms for the maximum weight independent set problem (MWIS) in the same class of graphs is presented. The technique consists of solving an LP-relaxation of the MWIS problem with certain clique inequalities, constructing an instance of the vertex coloring problem from the LP solution, applying the coloring algorithm to this instance, and selecting the best resulting color class as the MWIS solution. The approximation ratio obtained is the product of the approximation ratio with which the LP formulation can be solved (usually equal to one) and the approximation ratio of the coloring algorithm with respect to the size of the largest relevant clique. Applying this technique, the best known approximation algorithms are obtained for the maximum weight edge-disjoint paths problem in bidirected trees and in bidirected two-dimensional meshes with row–column routing, and for time-constrained scheduling of weighted packets in the same topologies. These problems are also proved to be MAX SNP-hard.

We discuss the Precoloring Extension (PrExt) and the List Coloring (LiCol) problems for trees, partial k-trees and cographs in the decision and the construction versions. Both problems for partial k-trees are solved in linear time when the number of colors is bounded by a constant and in polynomial time for an unbounded number of colors. For trees, we improve this to linear time. In contrast to that, the two problems differ in complexity for cographs. While PrExt has a linear-time decision algorithm, LiCol is shown to be NP-complete. We give polynomial-time algorithms for the corresponding enumeration problems # PrExt and # LiCol on partial k-trees and trees and for # PrExt on cographs.

In this paper we consider the following time constrained scheduling problem. Given a set of jobsJwith execution timese(j)∈(0, 1] and an undirected graphG=(J, E), we consider the problem to find a schedule for the jobs such that adjacent jobs (j, j′)∈Eare assigned to different machines and that the total execution time for each machine is at most 1. The goal is to find a minimum number of machines to execute all jobs under this time constraint. This scheduling problem is a natural generalization of the classical bin-packing problem. We propose and analyse several approximation algorithms with constant absolute worst case ratio for graphs that can be colored in polynomial time.

In this paper, we consider the mutual exclusion scheduling problem for comparability graphs. Given an undirected graph G and a fixed constant m, the problem is to find a minimum coloring of G such that each color is used at most m times. The complexity of this problem for comparability graphs was mentioned as an open problem by Möhring [Problem 9.10, in: I. Rival (Ed.), Graphs and Orders, Reidel, Dordrecht, 1985, p. 583] and for permutation graphs (a subclass of comparability graphs) as an open problem by Lonc [On complexity of some chain and antichain partition problem, in: G. Schmidt, R. Berghammer (Eds.), Graph Theoretical Concepts in Computer Science, WG 91, Lecture Notes in Computer Science, vol. 570, 1999, pp. 97–104]. We prove that this problem is already NP-complete for permutation graphs and for each fixed constant m⩾6.

In this paper we analyze a scheduling problem where each job j ϵ J is executed in dependence to a branching forest. We have a set of processor types P with a price c(p) for each processor of type p ϵ P. A job j processed on a processor of type pϵP has an execution time e(j,p) ϵ N . Given a deadline d ϵ N , we consider the problem to select a minimum cost set of processors (allowing an unlimited number of each type) for which there exists a schedule with makespan at most d. We propose an algorithm for the scheduling problem with approximation bound 0 (log¦J¦) .

Modern high-performance communication networks pose a number of challenging problems concerning the efficient allocation of resources to connection requests. In all-optical networks with wavelength-division multiplexing, connection requests must be assigned paths and colors (wavelengths) such that intersecting paths receive different colors, and the goal is to minimize the number of colors used. This path coloring problem is proved NP -hard for undirected and bidirected ring networks. Path coloring in undirected tree networks is shown to be equivalent to edge coloring of multigraphs, which implies a polynomial-time optimal algorithm for trees of constant degree as well as NP -hardness and an approximation algorithm with absolute approximation ratio 4 3 and asymptotic approximation ratio 1.1 for trees of arbitrary degree. For bidirected trees, path coloring is shown to be NP -hard even in the binary case. A polynomial-time optimal algorithm is given for path coloring in undirected or bidirected trees with n nodes under the assumption that the number of paths touching every single node of the tree is O (( log n) 1−e ) . Call scheduling is the problem of assigning paths and starting times to calls in a network with bandwidth reservation such that the maximum completion time is minimized. In the case of unit bandwidth requirements, unit edge capacities, and unit call durations, call scheduling is equivalent to path coloring. If either the bandwidth requirements or the call durations can be arbitrary, call scheduling is shown NP -hard for virtually every network topology.

In the grid computing paradigm, several clusters share their computing resources in order to distribute the workload. Each of the $N$ cluster is a set of $m$ identical processors (connected by a local interconnection network), and $n$ parallel jobs are submitted to a centralized queue. A job $J_j$ requires $q_j$ processors during $p_j$ units of time. We consider the Multiple Cluster Scheduling Problem ($\MCSP$), where the objective of is to schedule all the jobs in the clusters, minimizing the maximum completion time (makespan). This problem is closely related to the multiple strip packing problem, where the objective is to pack $n$ rectangles into $m$ strips of width $1$, minimizing the maximum height over all the strips. $\MCSP$ is $2$-inapproximable (unless $P=NP$), and several approximation algorithm have been proposed. However, ratio $2$ has only been reached by algorithms that use extremely costly and complex subroutines as "black boxes" (for example area maximization subroutines on a constant ($\approx 10^4$) number of bins, of $PTAS$ for the classical $P||C_{max}$ problem). Thus, our objective is to find a reasonable restriction of $\MCSP$ where the inapproximability lower bound could be tightened in almost linear time. In this spirit we study a restriction of $\MCSP$ where jobs do not require strictly more than half of the processors, and we provide for this problem a $2$-approximation running in $O(log_2(nh_{max})n(N+log(n)))$, where $h_{max}$ is the maximum processing time of a job. This result is somehow optimal, as this restriction of $\MCSP$ (and even simpler ones, where jobs require less than $\frac{m}{c}$, $c \in \mathbb{N}, c \ge 2$) remain $2$-innapproximable unless $\P=\NP$.

A vertex (edge) coloring $\phi:V\rightarrow \{1,2,\ldots ,t\}$ ($\phi':E\rightarrow \{1,2,\ldots,$ $t\}$) of a graph G=(V,E) is a vertex (edge) t-ranking if, for any two vertices (edges) of the same color, every path between them contains a vertex (edge) of larger color. The {\em vertex ranking number} $\chi_{r}(G)$ ({\em edge ranking number} $\chi_{r}'(G)$) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the {\sc Vertex Ranking} and {\sc Edge Ranking} problems. It is shown that $\chi_{r}(G)$ can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize the graphs where the vertex ranking number $\chi_{r}$ and the chromatic number $\chi$ coincide on all induced subgraphs, show that $\chi_{r}(G)=\chi (G)$ implies $\chi (G)=\omega (G)$ (largest clique size), and give a formula for $\chi_{r}'(K_n)$.

We study an important case of ILPs $\max\{c^Tx \ \vert\ \mathcal Ax = b, l \leq x \leq u,\, x \in \mathbb{Z}^{n t} \} $ with $n\cdot t$ variables and lower and upper bounds $\ell, u\in\mathbb Z^{nt}$. In $n$-fold ILPs non-zero entries only appear in the first $r$ rows of the matrix $\mathcal A$ and in small blocks of size $s\times t$ along the diagonal underneath. Despite this restriction many optimization problems can be expressed in this form. It is known that $n$-fold ILPs can be solved in FPT time regarding the parameters $s, r,$ and $\Delta$, where $\Delta$ is the greatest absolute value of an entry in $\mathcal A$. The state-of-the-art technique is a local search algorithm that subsequently moves in an improving direction. Both, the number of iterations and the search for such an improving direction take time $\Omega(n)$, leading to a quadratic running time in $n$. We introduce a technique based on Color Coding, which allows us to compute these improving directions in logarithmic time after a single initialization step. This leads to the first algorithm for $n$-fold ILPs with a running time that is near-linear in the number $nt$ of variables, namely $(rs\Delta)^{O(r^2s + s^2)} L^2 \cdot nt \log^{O(1)}(nt)$, where $L$ is the encoding length of the largest integer in the input. In contrast to the algorithms in recent literature, we do not need to solve the LP relaxation in order to handle unbounded variables. Instead, we give a structural lemma to introduce appropriate bounds. If, on the other hand, we are given such an LP solution, the running time can be decreased by a factor of $L$.

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form $$\min \{c^T x \mid {\mathcal {A}} x = b, \ell \le x \le u, x \in {\mathbb {Z}}^{r + ns} \}$$ min { c T x ∣ A x = b , ℓ ≤ x ≤ u , x ∈ Z r + n s } where the constraint matrix $${\mathcal {A}} \in {\mathbb {Z}}^{nt \times r +ns}$$ A ∈ Z n t × r + n s consists of n matrices $$A_i \in {\mathbb {Z}}^{t \times r}$$ A i ∈ Z t × r on the vertical line and n matrices $$B_i \in {\mathbb {Z}}^{t \times s}$$ B i ∈ Z t × s on the diagonal line aside. We show a stronger hardness result for a number theoretic problem called Quadratic Congruences where the objective is to compute a number $$z \le \gamma $$ z ≤ γ satisfying $$z^2 \equiv \alpha \bmod \beta $$ z 2 ≡ α mod β for given $$\alpha , \beta , \gamma \in {\mathbb {Z}}$$ α , β , γ ∈ Z . This problem was proven to be NP-hard already in 1978 by Manders and Adleman. However, this hardness only applies for instances where the prime factorization of $$\beta $$ β admits large multiplicities of each prime number. We circumvent this necessity proving that the problem remains NP-hard, even if each prime number only occurs constantly often. Using this new hardness result for the $$\textsc {Quadratic Congruences}$$ Q U A D R A T I C C O N G R U E N C E S problem, we prove a lower bound of $$2^{2^{\delta (s+t)}} |I|^{O(1)}$$ 2 2 δ ( s + t ) | I | O ( 1 ) for some $$\delta > 0$$ δ > 0 for the running time of any algorithm solving 2-stage stochastic ILPs assuming the Exponential Time Hypothesis (ETH). Here, |I| is the encoding length of the instance. This result even holds if r, $$||b||_{\infty }$$ | | b | | ∞ , $$||c||_{\infty }, ||\ell ||_{\infty }$$ | | c | | ∞ , | | ℓ | | ∞ and the largest absolute value $$\varDelta $$ Δ in the constraint matrix $${\mathcal {A}}$$ A are constant. This shows that the state-of-the-art algorithms are nearly tight. Further, it proves the suspicion that these ILPs are indeed harder to solve than the closely related $$n$$ n -fold ILPs where the constraint matrix is the transpose of $${\mathcal {A}}$$ A .

The problem of establishing and completing a given set of calls as early as possible is studied for bidirectional and directed calls in various classes of networks. Even under the assumption of unit bandwidth requirements and unit call durations, call scheduling is NP-hard for trees with unbounded degree, for rings, and for meshes. Whereas bidirectional calls can be scheduled optimally in polynomial time for trees of constant degree, the problem for directed calls is already NP-hard for binary trees. Approximation algorithms with a constant performance ratio are known for many NP-hard variants of call scheduling.

In Germany the majority of people living with HIV/AIDS are males and little is known about the characteristics and epidemiology of female HIV patients. The German KompNetKohort is a large, national retro- and prospective, multicenter, HIV-specific cohort, that documents HIV-positive patients since 1991. One important question we wanted to answer is in how much these two populations differ and whether a gender specific treatment approach is needed. Supplement: Abstracts of the Tenth International Congress on Drug Therapy in HIV Infection http://www.biomedcentral.com/content/pdf/1758-2652-13-S4-info.pdf Conference: Tenth International Congress on Drug Therapy in HIV Infection 7-11 November 2010 Glasgow, UK (Published: 8 November 2010) doi:10.1186/1758-2652-13-S4-P20 Cite this article as: Krznaric et al.: Sex matters: retrospective data collection on the date of commencement of ART for HIV-positive women and men in the German KompNet cohort (1991-2009). Journal of the International AIDS Society 2010 13(Suppl 4):P20. Full text: PubMed Central: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3112983/

Optimal time of HAART initiation is still unknown. Several studies investigating this issue showed inconsistent results. Our study investigated whether there is a clinical benefit as to treated patients (pts) by an earlier start of therapy at CD4 between 350-449c/µl, compared to the range of 250-349c/µl. An analysis was conducted on basis of the open, retrospective and prospective, multi-center and nationwide cohort of the Competence Network for HIV/AIDS. Supplement: Abstracts of the Tenth International Congress on Drug Therapy in HIV Infection http://www.biomedcentral.com/content/pdf/1758-2652-13-S4-info.pdf Conference: Tenth International Congress on Drug Therapy in HIV Infection 7-11 November 2010 Glasgow, UK(Published: 8 November 2010) doi:10.1186/1758-2652-13-S4-P16 Cite this article as: Plettenberg et al.: Impact of timing HAART initiation on immune status and clinical course in the cohort of the German competence network for HIV/AIDS. Journal of the International AIDS Society 2010 13(Suppl 4):P16. Full text: PubMed Central: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3112938/