(r|p)-centroid problems on networks with vertex and edge demand

This paper analyzes (r|p)-centroid$(r|p)\mathrm{-}\mathrm{centroid}$ problems on networks with vertex and edge demand under a binary choice rule. Bilevel programming models are presented for the discrete problem class. Furthermore, NP-hardness proofs for the discrete and continuous (1|p)-centroid$(1|p)\mathrm{-}\mathrm{centroid}$ problem on general networks with edge demand only are provided. Nevertheless, an efficient algorithm to determine a discrete (1|p)-centroid$(1|p)\mathrm{-}\mathrm{centroid}$ of a tree network with vertex and edge demand can be derived.     

Three insertion heuristics and a justification improvement heuristic for two-dimensional bin packing with guillotine cuts

The problem of packing two-dimensional items into two-dimensional bins is considered in which patterns of items allocated to bins must be guillotine-cuttable and item rotation might be allowed (2BP|?|G)$(2\mathrm{BP}|?|\mathrm{G})$. Three new constructive heuristics, namely, first-fit insertion heuristic, best-fit insertion heuristic, and critical-fit insertion heuristic, and a new justification improvement heuristic are proposed. All new heuristics use tree structures to represent guillotine-cuttable patterns of items and proceed by inserting one item at a time in a partial solution. Central to all heuristics are a new procedure for enumerating possible insertions and a new fitness criterion for choosing the best insertion. All new heuristics have quadratic worst-case computational complexity except for the critical-fit insertion heuristic which has a cubic worst-case computational complexity. The efficiency and effectiveness of the proposed heuristics is demonstrated by comparing their empirical performance on a standard benchmark data set against other published approaches.     

A new heuristic recursive algorithm for the strip rectangular packing problem

A fast and new heuristic recursive algorithm to find a minimum height for two-dimensional strip rectangular packing problem is presented. This algorithm is mainly based on heuristic strategies and a recursive structure, and its average running time is T(n)=θ(n³)$T(n)=\theta (n^3)$. The computational results on a class of benchmark problems have shown that this algorithm not only finds shorter height than the known meta-heuristic ones, but also runs in shorter time. Especially for large test problems, it performs better.     

A self-stabilizing algorithm to maximal 2-packing with improved complexity

In self-stabilization, each node has a local view of the distributed network system, in a finite amount of time the system converges to a global setup with desired property, in this case establishing a 2-packing set. Using a graph G=(V,E)$G=(V,E)$ to represent the network, a subset S⊆V$S\subseteq V$ is a 2-packing if ∀i∈V:|N[i]∩S|?1$\forall i\in V:|N[i]\cap S|?1$. In this paper, we first propose an ID-based, constant space, self-stabilizing algorithm that stabilizes to a maximal 2-packing in an arbitrary graph. We show that the algorithm stabilizes in O(mn)$O(mn)$ moves under any scheduler (such as a distributed daemon). Secondly, we show that the algorithm stabilizes in O(n²)$O(n^2)$ rounds under a synchronous daemon where every privileged node moves at each round.     

Asynchronous deterministic rendezvous in graphs

Two mobile agents (robots) having distinct labels and located in nodes of an unknown anonymous connected graph have to meet. We consider the asynchronous version of this well-studied rendezvous problem and we seek fast deterministic algorithms for it. Since in the asynchronous setting, meeting at a node, which is normally required in rendezvous, is in general impossible, we relax the demand by allowing meeting of the agents inside an edge as well. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of edge traversals of both agents until rendezvous is achieved. If agents are initially situated at a distance D   in an infinite line, we show a rendezvous algorithm with cost O(D|_Lmin|²)$\mathrm{O}(D|L_{\min }{|}^2)$ when D   is known and O((D+|_Lmax|)³)$\mathrm{O}((D+\left|L_{\max }\right|{)}^3)$ if D   is unknown, where |_Lmin|$\left|L_{\min }\right|$ and |_Lmax|$\left|L_{\max }\right|$ are the lengths of the shorter and longer label of the agents, respectively. These results still hold for the case of the ring of unknown size, but then we also give an optimal algorithm of cost O(n|_Lmin|)$\mathrm{O}(n|L_{\min }|)$, if the size n   of the ring is known, and of cost O(n|_Lmax|)$\mathrm{O}(n|L_{\max }|)$, if it is unknown. For arbitrary graphs, we show that rendezvous is feasible if an upper bound on the size of the graph is known and we give an optimal algorithm of cost O(D|_Lmin|)$\mathrm{O}(D|L_{\min }|)$ if the topology of the graph and the initial positions are known to agents.     

A sufficient condition involving implicit degree and neighborhood intersection for long cycles

Let id(v)$\mathit{id}(v)$ denote the implicit degree of a vertex v in a graph G. In this paper, we prove that: Let G   be a 2-connected graph. If max?{id(u),id(v)}≥c/2$\max ?\{\mathit{id}(u),\mathit{id}(v)\}\ge c/2$ for each pair of nonadjacent vertices u and v   in an induced claw, and |N(x)∩N(y)|≥2$|N(x)\cap N(y)|\ge 2$ for each pair of nonadjacent vertices x and y in an induced modified claw, then G contains either a hamiltonian cycle or a cycle of length at least c.     

Flip-pushdown automata with k pushdown reversals and E0L systems are incomparable

We prove that any propagating E0L system cannot generate the language {w#w|w∈{0,1}^?}$\{w\mathrm{\#}w|w\in {\{0,1\}}^{?}\}$. This result, together with some known ones, enables us to conclude that the flip-pushdown automata with k pushdown reversals, i.e., the pushdown automata with the ability to flip the pushdown, and E0L systems are incomparable. This result solves an open problem stated by Holzer and Kutrib in 2003.     

Approximation algorithms for facility location problems with a special class of subadditive cost functions

In this article we focus on approximation algorithms for facility location problems with subadditive costs. As examples of such problems, we present three facility location problems with stochastic demand and exponential servers, respectively inventory. We present a (1+ε,1)$(1+\epsilon ,1)$-reduction of the facility location problem with subadditive costs to the soft capacitated facility location problem, which implies the existence of a 2(1+ε)$2(1+\epsilon )$-approximation algorithm. For a special subclass of subadditive functions, we obtain a 2-approximation algorithm by reduction to the linear cost facility location problem.     

First steps to the runtime complexity analysis of ant colony optimization

The paper presents results on the runtime complexity of two ant colony optimization (ACO) algorithms: ant system, the oldest ACO variant, and GBAS, the first ACO variant for which theoretical convergence results have been established. In both cases, as the class of test problems under consideration, a slight generalization of the well-known OneMax test function has been chosen. The techniques used for the runtime analysis of the two algorithms differ: in the case of GBAS, the expected runtime until the optimal solution is reached is studied by a direct bound estimation approach inspired by comparable results for the (1+1)$(1+1)$ evolutionary algorithm (EA). A runtime bound of order O(mlogm)$O(m\log m)$, where m   is the problem instance size, is obtained. In the case of ant system, the original discrete stochastic process is approximated by a suitable continuous deterministic process. The validity of the approximation is shown by means of a rigid convergence theorem exploiting a classical result from mathematical learning theory. Using this approximation, it is demonstrated that for the considered OneMax-type problems, a runtime of order O(mlog(1/ε))$O(m\log (1/\epsilon ))$ until reaching an expected relative   solution quality of 1-ε$1-\epsilon$, and a runtime of O(mlogm)$O(m\log m)$ until reaching the optimal   solution with high probability can be predicted. Our results are the first to show competitiveness in runtime complexity with (1+1$1+1$) EA on OneMax for a proper ACO algorithm.     

Approximation algorithms for the arc orienteering problem

In this article we present approximation algorithms for the Arc Orienteering Problem (AOP). We propose a polylogarithmic approximation algorithm in directed graphs, while in undirected graphs we give a (6+?+o(1))$(6+?+o(1))$ and a (4+?)$(4+?)$-approximation algorithm for arbitrary instances and instances of unit profit, respectively. Also, an inapproximability result for the AOP is obtained as well as approximation algorithms for the Mixed Orienteering Problem.     

On approximating metric 1-median in sublinear time

This paper focuses on approximating the metric 1-median problem with sublinear number of queries and time complexity. We first show a simper proof of the currently best 4-approximation algorithm, and then propose a recursive algorithm. For any integer h?2$h?2$, the algorithm finds a 2h  -approximation solution with O(n^1+1/h)$O(n^{1+1/h})$ queries and time complexity.     

Practical perfect hashing in nearly optimal space

A hash function is a mapping from a key universe U   to a range of integers, i.e., h:U?{0,1,…,m−1}$h:U?\{\mathrm{0,1},\dots ,m-1\}$, where m is the range's size. A perfect hash function   for some set S⊆U$S\subseteq U$ is a hash function that is one-to-one on S  , where m≥|S|$m\ge \left|S\right|$. A minimal perfect hash function   for some set S⊆U$S\subseteq U$ is a perfect hash function with a range of minimum size, i.e., m=|S|$m=\left|S\right|$. This paper presents a construction for (minimal) perfect hash functions that combines theoretical analysis, practical performance, expected linear construction time and nearly optimal space consumption for the data structure. For n keys and m=n   the space consumption ranges from 2.62n+o(n)$2.62n+o(n)$ to 3.3n+o(n)$3.3n+o(n)$ bits, and for m=1.23n$m=1.23n$ it ranges from 1.95n+o(n)$1.95n+o(n)$ to 2.7n+o(n)$2.7n+o(n)$ bits. This is within a small constant factor from the theoretical lower bounds of 1.44n$1.44n$ bits for m=n   and 0.89n$0.89n$ bits for m=1.23n$m=1.23n$. We combine several theoretical results into a practical solution that has turned perfect hashing into a very compact data structure to solve the membership problem when the key set S is static and known in advance. By taking into account the memory hierarchy we can construct (minimal) perfect hash functions for over a billion keys in 46 min using a commodity PC. An open source implementation of the algorithms is available at http://cmph.sf.net under the GNU Lesser General Public License (LGPL).     

On the partition dimension of a class of circulant graphs

For a vertex v   of a connected graph G(V,E)$G(V,E)$ and a subset S of V, the distance between a vertex v and S   is defined by d(v,S)=min{d(v,x):x∈S}$d(v,S)=\min \{d(v,x):x\in S\}$. For an ordered k  -partition π={_S1,_S2…_Sk}$\pi =\{S_1,S_2\dots S_k\}$ of V, the partition representation of v with respect to π is the k  -vector r(v|π)=(d(v,_S1),d(v,_S2)…d(v,_Sk))$r(v|\pi )=(d(v,S_1),d(v,S_2)\dots d(v,S_k))$. The k-partition π is a resolving partition if the k  -vectors r(v|π)$r(v|\pi )$, v∈V(G)$v\in V(G)$ are distinct. The minimum k for which there is a resolving k-partition of V is the partition dimension of G. Salman et al. [1] in their paper which appeared in Acta Mathematica Sinica, English Series   proved that partition dimension of a class of circulant graph G(n,±{1,2})$G(n,\pm \{1,2\})$, for all even n?6$n?6$ is four. In this paper we prove that it is three.     

On hypercube packings,blocking sets and a covering problem

Consider sets S of hypercubes of side 2 in the discrete n-dimensional torus of side 4 with the property that every possible hypercube of side 2 has a nonempty intersection with some hypercube in S. The problem of minimizing the size of S is studied in two settings, depending on whether intersections between hypercubes in S are allowed or not. If intersections are not allowed, then one is asking for the smallest size of a non-extensible packing S  ; this size is denoted by f(n)$f(n)$. If intersections are allowed, then the structure S is called a blocking set. The smallest size of a blocking set S   is denoted by h(n)$h(n)$. By computer-aided techniques, it is shown that f(5)=12$f(5)=12$, f(6)=16$f(6)=16$, h(6)=15$h(6)=15$ and h(7)≤23$h(7)\le 23$. Also, non-extensible packings as well as blocking sets of certain small sizes are classified for n≤6$n\le 6$. There is a direct connection between these problems and a covering problem originating from the football pools.     

Optimal fault-tolerant embedding of paths in twisted cubes

The twisted cube is an important variation of the hypercube. It possesses many desirable properties for interconnection networks. In this paper, we study fault-tolerant embedding of paths in twisted cubes. Let _TQn(V,E)${\mathit{TQ}}_n(V,E)$ denote the n-dimensional twisted cube. We prove that a path of length l   can be embedded between any two distinct nodes with dilation 1 for any faulty set F⊂V(_TQn)∪E(_TQn)$F\subset V({\mathit{TQ}}_n)\cup E({\mathit{TQ}}_n)$ with |F|?n-3$\left|F\right|?n-3$ and any integer l   with 2^n-1-1?l?|V(_TQn-F)|-1$2^{n-1}-1?l?|V({\mathit{TQ}}_n-F)|-1$ (n?3$n?3$). This result is optimal in the sense that the embedding has the smallest dilation 1. The result is also complete in the sense that the two bounds on path length l   and faulty set size |F|$\left|F\right|$ for a successful embedding are tight. That is, the result does not hold if l?2^n-1-2$l?2^{n-1}-2$ or |F|?n-2$\left|F\right|?n-2$. We also extend the result on (n-3)$(n-3)$-Hamiltonian connectivity of _TQn${\mathit{TQ}}_n$ in the literature.     

Fast algorithms for some dominating induced matching problems

We describe O(n)$O(n)$ time algorithms for finding the minimum weighted dominating induced matching of chordal, dually chordal, biconvex, and claw-free graphs. For the first three classes, we prove tight O(n)$O(n)$ bounds on the maximum number of edges that a graph having a dominating induced matching may contain. By applying these bounds, and employing existing O(n+m)$O(n+m)$ time algorithms we show that they can be reduced to O(n)$O(n)$ time. For claw-free graphs, we describe a variation of the existing algorithm for solving the unweighted version of the problem, which decreases its complexity from O(n²)$O(n^2)$ to O(n)$O(n)$, while additionally solving the weighted version. The same algorithm can be easily modified to count the number of DIM's of the given graph.     

Metaheuristic approaches for the two-machine flow-shop problem with weighted late work criterion and common due date

In this paper, metaheuristic approaches for the two-machine flow-shop problem with a common due date and the weighted late work performance measure (F2|_dj=d|_Yw)$(F2|d_j=d|Y_w)$ are presented. The late work criterion estimates the quality of a solution with regard to the duration of the late parts of jobs, not taking into account the quantity of the delay for the fully late activities. Since the problem mentioned is known to be NP-hard, three trajectory methods, namely simulated annealing, tabu search and variable neighborhood search are proposed based on the special features of the case under consideration. Then, the results of computational experiments are reported, in which the metaheuristics were compared one to each other, as well to an exact approach and a list scheduling algorithm.