An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines

We propose an off-line delayed-start LPT algorithm that sequences the first (longest) 5 jobs optimally and the remaining jobs according to the LPT principle on two identical parallel machines. We show that this algorithm has a sharper tight worst-case ratio bound than the traditional LPT algorithm for the sum of squares of machine completion times minimization problem.     

The maximum integer multiterminal flow problem in directed graphs

Given an arc-capacitated digraph and k terminal vertices, the directed maximum integer multiterminal flow problem is to route the maximum number of flow units between the terminals. We introduce a new parameter k_L?k for this problem and study its complexity with respect to k_L.     

The firefighter problem for graphs of maximum degree three

We show that the firefighter problem is NP-complete for trees of maximum degree three, but in P for graphs of maximum degree three if the fire breaks out at a vertex of degree at most two.     

A better approximation algorithm for the budget prize collecting tree problem

Given an undirected graph G=(V,E), an edge cost c(e)?0 for each edge e∈E, a vertex prize p(v)?0 for each vertex v∈V, and an edge budget B. The BUDGET PRIZE COLLECTING TREE PROBLEM is to find a subtree T′=(V′,E′) that maximizes , subject to . We present a (4+ε)-approximation algorithm.     

Local approximations for maximum partial subgraph problem

We deal with MAXH₀-FREE PARTIAL SUBGRAPH. We mainly prove that 3-locally optimum solutions achieve approximation ratio (δ₀+1)/(B+2+ν₀), where B=max_v∈Vd_G(v), δ₀=min_v∈V(H0)d_H0(v) and ν₀=(|V(H₀)|+1)/δ₀. Next, we show that this ratio rises up to 3/(B+1) when H₀=K₃. Finally, we provide hardness results for MAXK₃-FREE PARTIAL SUBGRAPH.     

Approximating maximum edge 2-coloring in simple graphs

We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of roughly 0.842 and runs in O(n³m) time, where n (respectively, m) is the number of vertices (respectively, edges) in the input graph. The previously best ratio achieved by a polynomial-time approximation algorithm was .     

The approximation gap for the metric facility location problem is not yet closed

We consider the 1.52-approximation algorithm of Mahdian et al. for the metric uncapacitated facility location problem. We show that their algorithm does not close the gap with the lower bound on approximability, 1.463, by providing a construction of instances for which its approximation ratio is not better than 1.494.     

Reoptimization of minimum and maximum traveling salesman's tours

In this paper, reoptimization versions of the traveling salesman problem (TSP) are addressed. Assume that an optimum solution of an instance is given and the goal is to determine if one can maintain a good solution when the instance is subject to minor modifications. We study the case where nodes are inserted in, or deleted from, the graph. When inserting a node, we show that the reoptimization problem for MinTSP is approximable within ratio 4/3 if the distance matrix is metric. We show that, dealing with metric MaxTSP, a simple heuristic is asymptotically optimum when a constant number of nodes are inserted. In the general case, we propose a 4/5-approximation algorithm for the reoptimization version of MaxTSP.     

A new approximation algorithm for the multilevel facility location problem

In this paper we propose a new integer programming formulation for the multilevel facility location problem and a novel 3-approximation algorithm based on LP-rounding. The linear program that we use has a polynomial number of variables and constraints, thus being more efficient than the one commonly used in the approximation algorithms for these types of problems.     

The maximum clique problem

In this paper we present a survey of results concerning algorithms, complexity, and applications of the maximum clique problem. We discuss enumerative and exact algorithms, heuristics, and a variety of other proposed methods. An up to date bibliography on the maximum clique and related problems is also provided.     

Computational analysis of counter-based schemes for VLSI test pattern generation

The use of a binary counter as a mechanism for VLSI built-in test pattern generation is examined. Four different schemes are studied which are defined as partitioning problems on the rows of a binary matrix T. The goal in all problems is to minimize the maximum distance between the values of the binary patterns of any two rows of T, so that they can be generated by a counter in the minimum number of cycles. Although all schemes are NP-hard, an approximation algorithm is presented for the first scheme which guarantees solutions within 2·p from the optimal, where p is the prescribed number of partitions. The remaining problems are shown to be NP-complete even to be approximated within twice the optimal.     

On the complexity of the k-customer vehicle routing problem

We investigate the complexity of the k-CUSTOMER VEHICLE ROUTING PROBLEM: Given an edge weighted graph, the problem requires to compute a minimum weight set of cyclic routes such that each contains a distinguished depot vertex and at most other k customer vertices, and every customer belongs to exactly one route.     

An approximation algorithm for the wireless gathering problem

The Wireless Gathering Problem is to find an interference-free schedule for data gathering in a wireless network in minimum time. We present a 4-approximate polynomial-time on-line algorithm for this NP-hard problem. We show that no shortest path following algorithm can have an approximation ratio better than 4.     

Laplacian eigenvalues and the maximum cut problem

We introduce and study an eigenvalue upper bound(G) on the maximum cut mc (G) of a weighted graph. The function(G) has several interesting properties that resemble the behaviour of mc (G). The following results are presented.We show that is subadditive with respect to amalgam, and additive with respect to disjoint sum and 1-sum. We prove that(G) is never worse that 1.131 mc(G) for a planar, or more generally, a weakly bipartite graph with nonnegative edge weights. We give a dual characterization of(G), and show that(G) is computable in polynomial time with an arbitrary precision.The research has been partially done when the second author visited LRI in September 1989.