An exponential (matching based) neighborhood for the vehicle routing problem

We introduce an exponential neighborhood for the Vehicle Routing Problem (vrp) with unit customers’ demands, and we show that it can be explored efficiently in polynomial time by reducing its exploration to a particular case of the Restricted Complete Matching (rcm) problem that we prove to be polynomial time solvable using flow techniques. Furthermore, we show that in the general case with non-unit customers’ demands the exploration of the neighborhood becomes an -hard problem.     

A Polynomial Time Approximation Scheme for the Problem of Interconnecting Highways

The objective of the Interconnecting Highways problem is to construct roads of minimum total length to interconnect n given highways under the constraint that the roads can intersect each highway only at one point in a designated interval which is a line segment. We present a polynomial time approximation scheme for this problem by applying Arora's framework (Arora, 1998; also available from http:www.cs.princeton.edu/~arora). For every fixed c > 1 and given any n line segments in the plane, a randomized version of the scheme finds a -approximation to the optimal cost in O(n ^O(c)log(n) time.     

Parameterized dominating set problem in chordal graphs: complexity and lower bound

In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine whether a given chordal graph G=(V,E) contains a dominating set of size k or not, where k is an integer parameter. We show that the problem is W[1]-hard and it cannot be solved in time unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved to when the underlying graph G is an interval graph.     

A note on anti-coordination and social interactions

This note confirms a conjecture of (Bramoullé in Games Econ Behav 58:30–49, 2007). The problem, which we name the maximum independent cut problem, is a restricted version of the MAX-CUT problem, requiring one side of the cut to be an independent set. We show that the maximum independent cut problem does not admit any polynomial time algorithm with approximation ratio better than n ^1?? , where n is the number of nodes, and ? arbitrarily small, unless $\mathrm{P} = \mathrm{NP}$ . For the rather special case where each node has a degree of at most four, the problem is still APX-hard.     

Performance ratios of the Karmarkar-Karp differencing method

We consider the multiprocessor scheduling problem in which one must schedule n independent tasks nonpreemptively on m identical, parallel machines, such that the completion time of the last task is minimal. For this well-studied problem the Largest Differencing Method of Karmarkar and Karp outperforms other existing polynomial-time approximation algorithms from an average-case perspective. For m ≥ 3 the worst-case performance of the Largest Differencing Method has remained a challenging open problem. In this paper we show that the worst-case performance ratio is bounded between . For fixed m we establish further refined bounds in terms of n.     

Minimum diameter cost-constrained Steiner trees

Given an edge-weighted undirected graph $G=(V,E,c,w)$ where each edge $e\in E$ has a cost $c(e)\ge 0$ and another weight $w(e)\ge 0$ , a set $S\subseteq V$ of terminals and a given constant $\mathrm{C}_0\ge 0$ , the aim is to find a minimum diameter Steiner tree whose all terminals appear as leaves and the cost of tree is bounded by $\mathrm{C}_0$ . The diameter of a tree refers to the maximum weight of the path connecting two different leaves in the tree. This problem is called the minimum diameter cost-constrained Steiner tree problem, which is NP-hard even when the topology of the Steiner tree is fixed. In this paper, we deal with the fixed-topology restricted version. We prove the restricted version to be polynomially solvable when the topology is not part of the input and propose a weakly fully polynomial time approximation scheme (weakly FPTAS) when the topology is part of the input, which can find a $(1+\epsilon )$ –approximation of the restricted version problem for any $\epsilon >0$ with a specific characteristic.     

Optimal st-orientations for plane triangulations

For plane triangulations, it has been proved that there exists a plane triangulation G with n vertices such that for any st-orientation of G, the length of the longest directed paths of G in the st-orientation is (Zhang and He in Lecture Notes in Computer Science, vol. 3383, pp. 425–430, 2005). In this paper, we prove the bound is optimal by showing that every plane triangulation G with n-vertices admits an st-orientation with the length of its longest directed paths bounded by . In addition, this st-orientation is constructible in linear time. A by-product of this result is that every plane graph G with n vertices admits a visibility representation with height , constructible in linear time, which is also optimal. A preliminary version of this paper was presented at AAIM 2007.     

Improved Approximation for Breakpoint Graph Decomposition and Sorting by Reversals

Sorting by Reversals (SBR) is one of the most widely studied models of genome rearrangements in computational molecular biology. At present, is the best known approximation ratio achievable in polynomial time for SBR. A very closely related problem, called Breakpoint Graph Decomposition (BGD), calls for a largest collection of edge disjoint cycles in a suitably-defined graph. It has been shown that for almost all instances SBR is equivalent to BGD, in the sense that any solution of the latter corresponds to a solution of the former having the same value. In this paper, we show how to improve the approximation ratio achievable in polynomial time for BGD, from the previously known to for any > 0. Combined with the results in (Caprara, Journal of Combinatorial Optimization, vol. 3, pp. 149–182, 1999b), this yields the same approximation guarantee for n! – O((n – 5)!) out of the n! instances of SBR on permutations with n elements. Our result uses the best known approximation algorithms for Stable Set on graphs with maximum degree 4 as well as for Set Packing where the maximum size of a set is 6. Any improvement in the ratio achieved by these approximation algorithms will yield an automatic improvement of our result.     

2-Distance vertex-distinguishing index of subcubic graphs

This paper addresses the performance of scheduling algorithms for a two-stage no-wait hybrid flowshop environment with inter-stage flexibility, where there exist several parallel machines at each stage. Each job, composed of two operations, must be processed from start to completion without any interruption either on or between the two stages. For each job, the total processing time of its two operations is fixed, and the stage-1 operation is divided into two sub-parts: an obligatory part and an optional part (which is to be determined by a solution), with a constraint that no optional part of a job can be processed in parallel with an idleness of any stage-2 machine. The objective is to minimize the makespan. We prove that even for the special case with only one machine at each stage, this problem is strongly NP-hard. For the case with one machine at stage 1 and m machines at stage 2, we propose two polynomial time approximation algorithms with worst case ratio of \(3-\frac{2}{m+1}\) and \(2-\frac{1}{m+1}\), respectively. For the case with m machines at stage 1 and one machine at stage 2, we propose a polynomial time approximation algorithm with worst case ratio of 2. We also prove that all the worst case ratios are tight.     

Inapproximability results for the lateral gene transfer problem

This paper concerns the Lateral Gene Transfer Problem. This minimization problem, defined by Hallett and Lagergren (2001), is that of finding the most parsimonious lateral gene transfer scenario for a given pair of gene and species trees. Our main results are the following:

Minimizing the total cost of barrier coverage in a linear domain

Barrier coverage, as one of the most important applications of wireless sensor network (WSNs), is to provide coverage for the boundary of a target region. We study the barrier coverage problem by using a set of n sensors with adjustable coverage radii deployed along a line interval or circle. Our goal is to determine a range assignment \(\mathbf {R}=({r_{1}},{r_{2}}, \ldots , {r_{n}})\) of sensors such that the line interval or circle is fully covered and its total cost \(C(\mathbf {R})=\sum _{i=1}^n {r_{i}}^\alpha \) is minimized. For the line interval case, we formulate the barrier coverage problem of line-based offsets deployment, and present two approximation algorithms to solve it. One is an approximation algorithm of ratio 4 / 3 runs in \(O(n^{2})\) time, while the other is a fully polynomial time approximation scheme (FPTAS) of computational complexity \(O(\frac{n^{2}}{\epsilon })\). For the circle case, we optimally solve it when \(\alpha = 1\) and present a \(2(\frac{\pi }{2})^\alpha \)-approximation algorithm when \(\alpha > 1\). Besides, we propose an integer linear programming (ILP) to minimize the total cost of the barrier coverage problem such that each point of the line interval is covered by at least k sensors.     

On lazy bureaucrat scheduling with common deadlines

Lazy bureaucrat scheduling is a new class of scheduling problems introduced by Arkin et al. (Inf. Comput. 184:129–146, 2003). In this paper we focus on the case where all the jobs share a common deadline. Such a problem is denoted as CD-LBSP, which has been considered by Esfahbod et al. (Algorithms and data structures. Lecture notes in computer science, vol. 2748, pp. 59–66, 2003). We first show that the worst-case ratio of the algorithm SJF (Shortest Job First) is two under the objective function [min-time-spent], and thus answer an open question posed in (Esfahbod, et al. in Algorithms and data structures. Lecture notes in computer science, vol. 2748, pp. 59–66, 2003). We further present two approximation schemes A _k and B _k both having worst-case ratio of , for any given integer k>0, under the objective functions [min-makespan] and [min-time-spent], respectively. Finally, we prove that the problem CD-LBSP remains NP-hard under several objective functions, even if all jobs share the same release time. A preliminary version of the paper appeared in Proceedings of the 7th Latin American Symposium on Theoretical Informatics, pp 515–523, 2006. Research of G. Zhang supported in part by NSFC (60573020).     

Sublinear time width-bounded separators and their application to the protein side-chain packing problem

Given d>2 and a set of n grid points Q in ℜ ^d , we design a randomized algorithm that finds a w-wide separator, which is determined by a hyper-plane, in sublinear time such that Q has at most points on either side of the hyper-plane, and at most points within distance to the hyper-plane, where c _d is a constant for fixed d. In particular, c ₃=1.209. To our best knowledge, this is the first sublinear time algorithm for finding geometric separators. Our 3D separator is applied to derive an algorithm for the protein side-chain packing problem, which improves and simplifies the previous algorithm of Xu (Research in computational molecular biology, 9th annual international conference, pp. 408–422, 2005). This research is supported by Louisiana Board of Regents fund under contract number LEQSF(2004-07)-RD-A-35. The part of this research was done while Bin Fu was associated with the Department of Computer Science, University of New Orleans, LA 70148, USA and the Research Institute for Children, 200 Henry Clay Avenue, New Orleans, LA 70118, USA.     

Partitioning a weighted partial order

The problem of partitioning a partially ordered set into a minimum number of chains is a well-known problem. In this paper we study a generalization of this problem, where we not only assume that the chains have bounded size, but also that a weight w _i is given for each element i in the partial order such that w _i ≤w _j if i ≺ j. The problem is then to partition the partial order into a minimum-weight set of chains of bounded size, where the weight of a chain equals the weight of the heaviest element in the chain. We prove that this problem is -hard, and we propose and analyze lower bounds for this problem. Based on these lower bounds, we exhibit a 2-approximation algorithm, and show that it is tight. We report computational results for a number of real-world and randomly generated problem instances.     

Finding nucleolus of flow game

We study the algorithmic issues of finding the nucleolus of a flow game. The flow game is a cooperative game defined on a network D=(V,E;ω). The player set is E and the value of a coalition S⊆E is defined as the value of a maximum flow from source to sink in the subnetwork induced by S. We show that the nucleolus of the flow game defined on a simple network (ω(e)=1 for each e∈E) can be computed in polynomial time by a linear program duality approach, settling a twenty-three years old conjecture by Kalai and Zemel. In contrast, we prove that both the computation and the recognition of the nucleolus are -hard for flow games with general capacity. Supported by NCET, NSFC (10771200), a CERG grant (CityU 1136/04E) of Hong Kong RGC, an SRG grant (7001838) of City University of Hong Kong.     

Approximation algorithms for connected facility location problems

We study Connected Facility Location problems. We are given a connected graph G=(V,E) with nonnegative edge cost c _e for each edge e∈E, a set of clients D⊆V such that each client j∈D has positive demand d _j and a set of facilities F⊆V each has nonnegative opening cost f _i and capacity to serve all client demands. The objective is to open a subset of facilities, say , to assign each client j∈D to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost is minimized for a given input parameter M≥1. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55 (Swamy and Kumar in Algorithmica, 40:245–269, 2004). We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm.     

Batch-Processing Scheduling with Setup Times

The problem is to minimize the total weighted completion time on a single batch-processing machine with setup times. The machine can process a batch of at most B jobs at one time, and the processing time of a batch is given by the longest processing time among the jobs in the batch. The setup time of a batch is given by the largest setup time among the jobs in the batch. This batch-processing problem reduces to the ordinary uni-processor scheduling problem when B = 1. In this paper we focus on the extreme case of B = +, i.e. a batch can contain any number of jobs. We present in this paper a polynomial-time approximation algorithm for the problem with a performance guarantee of 2. We further show that a special case of the problem can be solved in polynomial time.     

Online scheduling on parallel machines with two GoS levels

This paper investigates the online scheduling problem on parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels. Hence each job and machine are labeled with the GoS levels, and each job can be processed by a particular machine only when the GoS level of the job is not less than that of the machine. The goal is to minimize the makespan. In this paper, we consider the problem with two GoS levels. It assumes that the GoS levels of the first k machines and the last m−k machines are 1 and 2, respectively. And every job has a GoS level of 1 alternatively or 2. We first prove the lower bound of the problem under consideration is at least 2. Then we discuss the performance of algorithm AW presented in Azar et al. (J. Algorithms 18:221–237, 1995) for the problem and show it has a tight bound of 4−1/m. Finally, we present an approximation algorithm with competitive ratio . Research supported by Natural Science Foundation of Zhejiang Province (Y605316) and its preliminary version appeared in Proceedings of AAIM2006, LNCS, 4041, 11-21.     

A “maximum node clustering” problem

In this note we introduce a graph problem, called Maximum Node Clustering (MNC). We prove that the problem (which is easily shown to be strongly NP-complete) can be approximated in polynomial time within a ratio arbitrarily close to 2. For the special case where the graph is a tree, the problem is NP-complete in the ordinary sense; for this case we present a pseudopolynomial algorithm based on dynamic programming, and a related Fully Polynomial Time Approximation Scheme (FPTAS). Also, the tree case is shown to be exactly solvable in time, where n is the number of nodes.     

Radiation hybrid map construction problem parameterized

In this paper, we study the Radiation hybrid map construction ( $\mathsf{{RHMC} }$ ) problem which is about reconstructing a genome from a set of gene clusters. The problem is known to be $\mathsf{{NP} }$ -complete even when all gene clusters are of size two and the corresponding problem ( $\mathsf{{RHMC}_2 }$ ) admits efficient constant-factor approximation algorithms. In this paper, for the first time, we consider the more general case when the gene clusters can have size either two or three ( $\mathsf{{RHMC}_3 }$ ). Let ${p\text{- }\mathsf {RHMC} }$ be a parameterized version of $\mathsf{{RHMC} }$ where the parameter is the size of solution. We present a linear kernel for ${p\text{- }\mathsf {RHMC}_3 }$ of size $22k$ that when combined with a bounded search-tree algorithm, gives an FPT algorithm running in $O(6^kk+n)$ time. For ${p\text{- }\mathsf {RHMC}_3 }$ we present a bounded search tree algorithm which runs in $O^*(2.45^k)$ time, greatly improving the previous bound using weak kernels.