Search

Abstract: In this paper, we consider a restricted variant of the scheduling problem, where the machines are the strategic players. For this multi-parameter mechanism design problem, the only known truthful mechanisms use task independent allocation algorithms and only have approximation ratio [N. Nisan, A. Ronen. Algorithmic mechanism design (extended abstract), in: STOC’99: Proceedings of the thirty-first annual ACM symposium on Theory of computing, ACM, New York, NY, USA, 1999. pp. 129–140; A. Mu’alem, M. Schapira, Setting lower bounds on truthfulness: Extended abstract, in: SODA’07: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2007, pp. 1143–1152; P. Lu, C. Yu, An improved randomized truthful mechanism for scheduling unrelated machines, in: 25th International Symposium on Theoretical Aspects of Computer Science, STACS, 2008, pp. 527–538; P. Lu, C. Yu, Randomized truthful mechanisms for scheduling unrelated machines, in: C.H. Papadimitriou, S. Zhang (Eds.), Proceedings of WINE, in: Lecture Notes in Computer Science, vol. 5385, Springer, 2008, pp. 402–413]. Lavi and Swamy first use the cycle monotone condition and design a 3-approximation truthful mechanism for a two value variant in [R. Lavi, C. Swamy, Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity, in: EC’07: Proceedings of the 8th ACM conference on Electronic commerce, ACM, New York, NY, USA, 2007, pp. 252–261], where the processing time of task on machine , say , can only be either a lower value or a higher value . We consider a generalized variant, where lies in and is a parameter satisfying some condition. We consider two special cases, case A when , and case B when ,, and give randomized truthful mechanisms with approximation ratio for both cases. Based on these two cases’ results, we are also able to deal with the general case of our two-range-values scheduling problem. We use a combination of two mechanisms, which is also a novel method in mechanism design for scheduling problems, and finally we give a randomized truthful mechanism with approximation ratio . Although the generalization seems a little incremental, we actually use a very novel technique in the key step of proving truthfulness for case A, as well as a new mechanism scheme for case B. Besides, the results in this paper are the first truthful mechanisms with constant approximation ratios when a machine (player) can report infinitely possible values, which is quite different from the two value variant, in which only finite values are available. Furthermore, together with Lavi and Swamy’s work, our results suggest that such a task-dependent approach can really do much better for the scheduling unrelated machines problem. [Copyright &y& Elsevier]

Motivated by the reconstruction of phylogenetic tree in biology, we study the full Steiner tree problem in this paper. Given a complete graph G=(V,E) with a length function on E and a proper subset R⊂V, the problem is to find a full Steiner tree of minimum length in G, which is a kind of Steiner tree with all the vertices of R as its leaves. In this paper, we show that this problem is NP-complete and MAX SNP-hard, even when the lengths of the edges are restricted to either 1 or 2. For the instances with lengths either 1 or 2, we give a 8/5-approximation algorithm to find an approximate solution for the problem. [Copyright &y& Elsevier]

A vertex subset C of a connected graph G is called a connected k -path vertex cover ( C V C P k ) if every path on k vertices contains at least one vertex from C , and the subgraph of G induced by C is connected. This concept originated in the field of security and supervisory control. This paper studies the minimum (weight) C V C P k problem. We first show that the minimum weight C V C P k problem can be solved in time O ( n ) when the graph is a tree, and can be solved in time O ( r n ) when the graph is a uni-cyclic graph whose unique cycle has length r , where n is the number of vertices. Making use of the algorithm on trees, we present a k -approximation algorithm for the minimum (cardinality) C V C P k problem under the assumption that the graph has girth at least k . An example is given showing that performance ratio k is asymptotically tight for our algorithm. [ABSTRACT FROM AUTHOR]

Although, the Hamiltonicity of solid grid graphs are polynomial-time decidable, the complexity of the longest cycle problem in these graphs is still open. In this paper, by presenting a linear-time constant-factor approximation algorithm, we show that the longest cycle problem in solid grid graphs is in APX. More precisely, our algorithm finds a cycle of length at least 2 n 3 + 1 in 2-connected n -node solid grid graphs. [ABSTRACT FROM AUTHOR]

Being the unbalanced version of the famous Min s – t Cut problem, the Min k -Size s – t Cut problem asks to find a k -size s – t cut with the minimum capacity, where a k -size s – t cut means an s – t cut with its s -side having size at most k . This problem is fundamental and has extensive applications, especially in community identification in social and information networks. It is known that the Min k -Size s – t Cut problem is NP-hard and can be approximated within O ( log ⁡ n ) , where n is the number of vertices in the input graph. In this paper, we give a new approximation algorithm for the Min k -Size s – t Cut problem based on the parametric flow technique. The algorithm is very simple and has only three lines to state. Its approximation ratio is k + 1 k + 1 − k ⁎ , where k ⁎ is the size of the s -side of an optimal solution. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider the problem of computing a minimum bending energy path (or MinBEP) in a simple corridor. Given a simple 2D corridor C bounded by straight line segments and arcs of radius 2r, the MinBEP problem is to compute a path P inside C and crossing two pre-specified points s and t located at each end of C so that the bending energy of P is minimized. For this problem, we first show how to lower bound the bending energy of an optimal curve with bounded curvature, and then use this lower bound to design a -approximation algorithm for this restricted version of the MinBEP problem. Our algorithm is based on a number of interesting geometric observations and approximation techniques on smooth curves, and can be easily implemented for practical purpose. It is the first algorithm with a guaranteed performance ratio for the MinBEP problem. [Copyright &y& Elsevier]

Abstract: This paper describes an extremely fast polynomial time algorithm, the Near Optimal Vertex Cover Algorithm (NOVCA) that produces an optimal or near optimal vertex cover for any known undirected graph G (V, E). NOVCA constructs the vertex cover by repeatedly adding, at each step, all vertices adjacent to the vertex of minimal degree; in the case of a tie, it selects the one having the maximum sum of degrees of its neighbors. The results identifying bounds on the size of the minimum vertex cover as well as polynomial complexity of algorithm are given with experimental verification. Future research efforts will be directed at tuning the algorithm and providing proof for better approximation ratio with NOVCA compared to any other available vertex cover algorithms. [Copyright &y& Elsevier]

Abstract: In the context of designing a scalable overlay network to support decentralized topic-based pub/sub communication, the Minimum Topic-Connected Overlay problem (Min-TCO in short) has been investigated: given a set of topics and a collection of users together with the lists of topics they are interested in, the aim is to connect these users to a network by a minimum number of edges such that every graph induced by users interested in a common topic is connected. It is known that Min-TCO is -hard and approximable within in polynomial time. In this paper, we further investigate the problem and some of its special instances. We give various hardness results for instances where the number of topics in which a user is interested in is bounded by a constant, and also for the instances where the number of users interested in a common topic is a constant. For the latter case, we present a first constant approximation algorithm. We also present some polynomial-time algorithms for very restricted instances of Min-TCO. [Copyright &y& Elsevier]

Abstract: In this paper we show that the problem of identifying an edge of a graph such that there exists an optimal vertex cover of containing exactly one of the vertices and is NP-hard. Such an edge is called a weak edge. We then develop a polynomial time approximation algorithm for the vertex cover problem with performance guarantee , where is an upper bound on a measure related to a weak edge of a graph. A related problem of identifying an edge such that there exists an optimal vertex cover containing both vertices and is also shown to be NP-hard. Further, we discuss a new relaxation of the vertex cover problem which is used in our approximation algorithm to obtain smaller values of . We also obtain linear programming representations of the vertex cover problem on special graphs. [Copyright &y& Elsevier]

Abstract: We consider the minimum rainbow subgraph problem (MRS): given a graph , whose edges are coloured with colours. Find a subgraph of of minimum order and with edges such that each colour occurs exactly once. For graphs with maximum degree there is a greedy polynomial-time approximation algorithm for the MRS problem with an approximation ratio of . In this paper we present a polynomial-time approximation algorithm with an approximation ratio of for . [ABSTRACT FROM AUTHOR]

Abstract: Given an underlying communication network represented as an edge-weighted graph , a source node , a set of destination nodes , and a capacity which is a positive integer, the capacitated multicast tree routing problem asks for a minimum cost routing scheme for source to send data to all destination nodes, under the constraint that in each routing tree at most destination nodes are allowed to receive the data copies. The cost of the routing scheme is the sum of the costs of all individual routing trees therein. Improving on our previous approximation algorithm for the problem, we present a new algorithm which achieves a worst case performance ratio of , where denotes the best known approximation ratio for the Steiner minimum tree problem. Since is about at the writing of the paper, the ratio achieved by our new algorithm is less than . In comparison, the previously best ratio was . [Copyright &y& Elsevier]

Abstract: The approximability of the unweighted independent set problem has been analyzed in terms of sparseness parameters such as the average degree and inductiveness. In the weighted case, no corresponding results are possible for average degree, since adding vertices of small weight can decrease the average degree arbitrarily without significantly changing the approximation ratio. In this paper, we introduce two weighted measures, namely weighted average degree and weighted inductiveness, and analyze algorithms for the weighted independent set problem in terms of these parameters. [Copyright &y& Elsevier]

In this paper, we study a problem of finding a vehicle scheduling to process a set of jobs which are located in an asymmetric metric space. Each job has a positive handling time , a time window , and a benefit . We consider the following two problems: MAX-VSP asks to find a schedule for a single vehicle to process a subset of jobs with the maximum benefit; and MIN-VSP asks to find a schedule to process all given jobs with the minimum number of vehicles. We first give an time algorithm that delivers a -approximate solution to MAX-VSP, where and is the maximum number of jobs that can be processed by the vehicle after processing a job and before visiting the processed job again by deadline . We then present an time algorithm that delivers a -approximate solution to MIN-VSP, where is the th harmonic number. [Copyright &y& Elsevier]

Abstract: This paper explores three concepts: the -center problem, some of its variants, and asymmetry. The -center problem is fundamental in location theory. Variants of -center may more accurately model real-life problems than the original formulation. Asymmetry is a significant impediment to approximation in many graph problems, such as -center, facility location, -median, and the TSP. We give an -approximation algorithm for the asymmetric weighted -center problem. Here, the vertices have weights and we are given a total budget for opening centers. In the p-neighbor variant each vertex must have (unweighted) centers nearby: we give an -bicriteria algorithm using centers, for small . Finally, we show the following three versions of the asymmetric -center problem to be inapproximable: priority -center, k-supplier, and outliers with forbidden centers. [Copyright &y& Elsevier]

We present a 0.7499-approximation algorithm for Max Set Splitting in this paper. The previously best known result for this problem is a 0.7240-approximation by Andersson and Engebretsen (Inform. Process. Lett. 65 (1998) 305), which is based on a semidefinite programming (SDP) relaxation. Our improvement is resulted from a strengthened SDP relaxation, an improved rounding method, and a tighter analysis compared with that in Andersson and Engebretsen (1998). [Copyright &y& Elsevier]

Given an edge-weighted tree T and an integer p⩾1, the minmax p-traveling salesmen problem on a tree T asks to find p tours such that the union of the p tours covers all the vertices. The objective is to minimize the maximum of length of the p tours. It is known that the problem is NP-hard and has a (2-2/(p+1))-approximation algorithm which runs in O(pp-1np-1) time for a tree with n vertices. In this paper, we consider an extension of the problem in which the set of vertices to be covered now can be chosen as a subset S of vertices and weights to process vertices in S are also introduced in the tour length. For the problem, we give an approximation algorithm that has the same performance guarantee, but runs in O((p-1)!·n) time. [Copyright &y& Elsevier]

We investigate the approximability of minimum and maximum linear ordering problems (MIN-LOP and MAX-LOP) and related feedback set problems such as maximum weight acyclic subdiagraph (MAX-W-SUBDAG), minimum weight feedback arc/vertex set (MIN-W-FAS/MIN-W-FVS) and a generalization of the latter called MIN-Subset-FAS/MIN-Subset-FVS. MAX-LOP and the other problems have been studied by many researchers but, though MIN-LOP arises in many practical contexts, it appears that it has not been studied before. In this paper, we first note that these minimization (respectively, maximization) problems are equivalent with respect to strict reduction and so have the same approximability properties. While MAX-LOP is APX-complete, MIN-LOP is only APX-hard. We conjecture that MIN-LOP is not in APX, unless P=NP. We obtain a result connecting extreme points of linear ordering polytope with approximability of MIN-LOP via LP-relaxation which seems to suggest that constant factor approximability of MIN-LOP may not be obtainable via this method. We also prove that (a) MIN-Subset-FAS cannot be approximated within a factor (1−ϵ) log n, for any ϵ>0, unless NP⊂DTIME(nlog log n), and (b) MIN-W-k-FAS, a generalization of MIN-LOP, is NPO-complete. We then show that Δt-MIN-LOP (respectively, Δt-MAX-LOP), in which the weight matrix satisfies a parametrized version of a stronger form of triangle inequality, with parameter t∈(0,2], is approximable within a factor (2+t)/2t (respectively, 4/(2+t)). We also show that these restricted versions are in PO iff t=2 and are not in PTAS for t∈(0,2), unless P=NP. [Copyright &y& Elsevier]

We study the problem of scheduling groups of tasks with precedence constraints on three dedicated processors. Each task requires a specified set of processors. Up to three precedence constraints are considered among groups of tasks requiring the same set of processors. The objective of the problem is to find a nonpreemptive schedule which minimizes the maximum completion time (makespan). This scheduling problem is equivalent to the problem of finding an extension of the constraint graph (i.e. the graph which represents the conflicts between tasks and the precedence constraints) to a comparability graph with minimum (over all the extensions) maximum clique weight. The problem is NP-hard in the strong sense. A normal schedule is such that all the tasks requiring the same set of processors are scheduled consecutively. With a normal schedule the problem reduces to the quotient graph of the constraint graph. In this paper we obtain tight approximation results for the minimum makespan of a normal schedule through tight results on the minimum increase of the maximum clique weight when the (partially oriented) quotient graph is extended to a comparability graph. [Copyright &y& Elsevier]

This paper considers ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times. Two objects of minimizing the latest job completion time and minimizing the latest machine completion time are studied. For the first objective, we present the optimal algorithms for m = 2, 3, 4 machine cases. For m ≥ 5, we propose an algorithm with competitive ratio 2 - 1/(m - 1) while the lower bound is SHAPE="SOL" ALIGN="C" STYLE="S">53. For the second objective, the optimal algorithm is also given. Furthermore, for a special case, an algorithm with significantly improved competitive ratio is given. [Copyright &y& Elsevier]