Springer Science and Business Media LLC

Multiprocessor job scheduling problem has become increasingly interesting, for both theoretical study and practical applications. Theoretical study of the problem has made significant progress recently, which, however, seems not to imply practical algorithms for the problem, yet. Practical algorithms have been developed only for systems with three processors and the techniques seem difficult to extend to systems with more than three processors. This paper offers new observations and introduces new techniques for the multiprocessor job scheduling problem on systems with four processors. A very simple and practical linear time approximation algorithm of ratio bounded by 1.5 is developed for the multi-processor job scheduling problem P 4|fix|C max, which significantly improves previous results. Our techniques are also useful for multiprocessor job scheduling problems on systems with more than four processors.

A graph $$G$$ has an efficient dominating set $$D \subseteq V(G)$$ if $$D$$ dominates every vertex exactly once. In this paper we introduce the study of the family $${S_k}$$ of graphs for which every $$G-S$$ is efficiently dominatable for $$0 \le |S|\le k$$ . Assuming that $$G$$ is efficiently dominatable, the efficiency index is the largest value k for which $$G$$ is in $$S_k$$ . A graph $$G$$ will be called super-efficient if every induced subgraph is efficiently dominatable. We give some characterizations for trees, grids, cylinders and torii to be super-efficient.

For a multigraph G = (V, E), let s ∈ V be a designated vertex which has an even degree, and let λ G (V − s) denote min{c G(X) | Ø ≠ X ⊂ V − s}, where c G(X) denotes the size of cut X. Splitting two adjacent edges (s, u) and (s, v) means deleting these edges and adding a new edge (u, v). For an integer k, splitting two edges e 1 and e 2 incident to s is called (k, s)-feasible if λG′(V − s) ≥ k holds in the resulting graph G′. In this paper, we prove that, for a planar graph G and an even k or k = 3 with k ≤ λ G (V − s), there exists a complete (k, s)-feasible splitting at s such that the resulting graph G′ is still planar, and present an O(n 3 log n) time algorithm for finding such a splitting, where n = |V|. However, for every odd k ≥ 5, there is a planar graph G with a vertex s which has no complete (k, s)-feasible and planarity-preserving splitting. As an application of this result, we show that for an outerplanar graph G and an even integer k the problem of optimally augmenting G to a k-edge-connected planar graph can be solved in O(n 3 log n) time.

We consider the problems of minimum-cost design and augmentation of directed network clusters that have diameter 2 and maintain the same diameter after the deletion of up to R elements (nodes or arcs) anywhere in the cluster. The property of a network to maintain not only the overall connectivity, but also the same diameter after the deletion of multiple nodes/arcs is referred to as strong attack tolerance. This paper presents the proof of NP-completeness of the decision version of the problem, derives tight theoretical bounds, as well as develops a heuristic algorithm for the considered problems, which are extremely challenging to solve to optimality even for small networks. Computational experiments suggest that the proposed heuristic algorithm does identify high-quality near-optimal solutions; moreover, in the special case of undirected networks with identical arc construction costs, the algorithm provably produces an exact optimal solution to strongly attack-tolerant two-hop network design problem, regardless of the network size.

This paper studies an online over-list model of the integrated allocation of berths and quay cranes (QCs) in container terminals with 1-lookahead ability. The objective is to minimize the maximum completion time of container vessels, i.e., the makespan. We focus on two different types of vessels, three berths and a small number of QCs in the hybrid berth layout, with 1-lookahead ability. We propose a $${{(1 + \sqrt{2} )/2}}$$ -competitive algorithm for the case with four cranes, a 5/4-competitive algorithm for the case with five cranes and a 4/3-competitive algorithm for the case with six cranes, respectively. All of the algorithms are proved to be optimal.

We present a primal-dual ⌈log(n)⌉-approximation algorithm for the version of the asymmetric prize collecting traveling salesman problem, where the objective is to find a directed tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. The previous algorithm for the problem (V.H. Nguyen and T.T Nguyen in Int. J. Math. Oper. Res. 4(3):294–301, 2012) which is not combinatorial, is based on the Held-Karp relaxation and heuristic methods such as the Frieze et al.’s heuristic (Frieze et al. in Networks 12:23–39, 1982) or the recent Asadpour et al.’s heuristic for the ATSP (Asadpour et al. in 21st ACM-SIAM symposium on discrete algorithms, 2010). Depending on which of the two heuristics is used, it gives respectively 1+⌈log(n)⌉ and $3+ 8\frac{\log(n)}{\log(\log(n))}$ as an approximation ratio. Our algorithm achieves an approximation ratio of ⌈log(n)⌉ which is weaker than $3+ 8\frac{\log(n)}{\log(\log(n))}$ but represents the first combinatorial approximation algorithm for the Asymmetric Prize-Collecting TSP.

Let $K_{n_{1},n_{2},\ldots,n_{m}}$ be a complete m-partite graph with partite sets of sizes n 1,n 2,…,n m . A complete m-partite graph is balanced if each partite set has n vertices. We denote this complete m-partite graph by K m(n). In this paper, we completely solve the problem of finding a maximum packing of the balanced complete m-partite graph K m(n), m odd, with edge-disjoint 5-cycles and we explicitly give the minimum leaves.

In this paper, we address the problem of online car-sharing with variable booking times (CSV for short). In this scenario, customers submit ride requests, each specifying two important time parameters: the booking time and the pick-up time (start time), as well as two location parameters—the pick-up location and the drop-off location within a graph. For each request, it’s important to note that it must be booked before its scheduled start time. The booking time can fall within a specific interval prior to the request’s starting time. Additionally, each car is capable of serving only one request at any given time. The primary objective of the scheduler is to optimize the utilization of k cars to serve as many requests as possible. As requests arrive at their booking times, the scheduler faces an immediate decision: whether to accept or decline the request. This decision must be made promptly upon request submission, precisely at the booking time. We prove that no deterministic online algorithm can achieve a competitive ratio smaller than $$L+1$$ even on a special case of a path (where L denotes the ratio between the largest and the smallest request travel time). For general graphs, we give a Greedy Algorithm that achieves $$(3L+1)$$ -competitive ratio for CSV. We also give a Parted Greedy Algorithm with competitive ratio $$(\frac{5}{2}L+10)$$ when the number of cars k is no less than $$\frac{5}{4}L+20$$ ; for CSV on a special case of a path, the competitive ratio of Parted Greedy Algorithm is $$(2L+10)$$ when $$k\ge L+20$$ .

Combinatorial filters, which take the form of labelled transition graphs, are a general representation for filtering and inference tasks in robotics. They are of particular interest in contexts where the objective is to minimize the computational resources needed to execute the filter. One specific problem is called the filter minimization (FM) problem, in which the goal is to find, for a given original filter, a state-minimal filter equivalent to the original filter. We consider a special case of FM, called the filter partitioning minimization (FPM) problem, in which the reduced filter must partition the state space of the original filter. This problem has been proven to be NP-hard. This paper considers the practical problem of solving FPM in spite of these hardness results. In contrast to the best known algorithm for this problem, a heuristic approach based on graph coloring proposed by O’Kane and Shell, we show how to convert an FPM instance to an instance of the well-known integer linear programming (ILP) problem. We present three distinct formulations of this reduction. Though ILP is itself a challenging problem, reducing FPM to ILP has the advantage that the ILP problem has been studied in great detail, and highly-optimized solvers are readily available. We describe experiments comparing this approach to the heuristic algorithm of O’Kane and Shell. The results show that the proposed ILP technique performs better in computing exact solutions as the filter sizes grow, and that the ILP approach obtains higher-quality feasible solutions, in contexts where time limitations prohibit the computation of exact solutions.