Motivated by the problem to approximate all feasible schedules by one schedule in a given scheduling environment,we introduce in this paper the concepts of strong simultaneous approximation ratio and weak simultaneous...Motivated by the problem to approximate all feasible schedules by one schedule in a given scheduling environment,we introduce in this paper the concepts of strong simultaneous approximation ratio and weak simultaneous approximation ratio.Then we study the two variants under various scheduling environments,such as non-preemptive,preemptive or fractional scheduling on identical,related or unrelated machines.展开更多
In this paper,a two-stage semi-hybrid flowshop problem which appears in graphics processing is studied. For this problem, there are two machines M1 and M2, and a set of independent jobs J= {J1 ,J2 ,…,Jn }. Each Ji co...In this paper,a two-stage semi-hybrid flowshop problem which appears in graphics processing is studied. For this problem, there are two machines M1 and M2, and a set of independent jobs J= {J1 ,J2 ,…,Jn }. Each Ji consists of two tasks Ai and Bi ,and task Ai must be completed before task Bi can start. Furthermore ,task Ai can be processed on M1 for ai time units ,or on Mw for ai^J time units ,while task Bi can only be processed on M2 for bi time units. Jobs and machines are available at time zero and no preemption is allowed. The objective is to minimize the maximum job completion time. It is showed that this problem is NP-hard. And a pseudo-polynomial time optimal algorithm is presented. A polynomial time approximation algorithm with worst-case ratio 2 is also presented.展开更多
Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of cro...Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. In many interesting cases, the algorithm performs better than the algorithms of Ye and of Halperin and Zwick. The main tool used to obtain this result is semidefinite programming.展开更多
In this paper,we consider approximation algorithms for optimizing a generic multivariate polynomial function in discrete(typically binary)variables.Such models have natural applications in graph theory,neural networks...In this paper,we consider approximation algorithms for optimizing a generic multivariate polynomial function in discrete(typically binary)variables.Such models have natural applications in graph theory,neural networks,error-correcting codes,among many others.In particular,we focus on three types of optimization models:(1)maximizing a homogeneous polynomial function in binary variables;(2)maximizing a homogeneous polynomial function in binary variables,mixed with variables under spherical constraints;(3)maximizing an inhomogeneous polynomial function in binary variables.We propose polynomial-time randomized approximation algorithms for such polynomial optimizationmodels,and establish the approximation ratios(or relative approximation ratios whenever appropriate)for the proposed algorithms.Some examples of applications for these models and algorithms are discussed as well.展开更多
Abstract We study the fleet size and mix vehicle routing problem with constraints on the capacity of each vehicle. The objective is to minimize the total cost including fixed utilization cost of vehicles and traveling...Abstract We study the fleet size and mix vehicle routing problem with constraints on the capacity of each vehicle. The objective is to minimize the total cost including fixed utilization cost of vehicles and traveling cost by vehicles. We give differential approximation algorithms for the fleet size and mix vehicle routing problem （FSMVRP） with two kinds of vehicles, the capacities of which are respectively nlk and n2k, n2 〉 nl ≥ 1, k ≥ 1. Using existing theories for vehicle routing problems and feature of the algorithms represented in the paper, we also prove that the algorithms give（1-6n＋3/（n＋1）2k＋n＋1）differential approximation ratio for （k, nk） VRP, n 〉 1and （1-6n2＋3n/n1k＋n2k）2k）differential approximation ratio for （nlk, n2k）VRP, n2 〉 nl 〉 1.展开更多
The paper briefly reviews NP-hard optimization problems and their inapproximability. The hardness of solving CLIQUE problem is specifically dis- cussed. A dynamic-programming algorithm and its improved version for CLI...The paper briefly reviews NP-hard optimization problems and their inapproximability. The hardness of solving CLIQUE problem is specifically dis- cussed. A dynamic-programming algorithm and its improved version for CLIQUE are reviewed and some additional analysis is presented. The analysis implies that the improved algorithm, HEWN (hierarchical edge-weighted network), only provides a heuristic or useful method, but cannot be called a polynomial algorithm.展开更多
基金The first author was supported by the National Natural Science Foundation of China(Nos.11601198 and 71761015)The second author was supported by the National Natural Science Foundation of China(No.11671368).
文摘Motivated by the problem to approximate all feasible schedules by one schedule in a given scheduling environment,we introduce in this paper the concepts of strong simultaneous approximation ratio and weak simultaneous approximation ratio.Then we study the two variants under various scheduling environments,such as non-preemptive,preemptive or fractional scheduling on identical,related or unrelated machines.
文摘In this paper,a two-stage semi-hybrid flowshop problem which appears in graphics processing is studied. For this problem, there are two machines M1 and M2, and a set of independent jobs J= {J1 ,J2 ,…,Jn }. Each Ji consists of two tasks Ai and Bi ,and task Ai must be completed before task Bi can start. Furthermore ,task Ai can be processed on M1 for ai time units ,or on Mw for ai^J time units ,while task Bi can only be processed on M2 for bi time units. Jobs and machines are available at time zero and no preemption is allowed. The objective is to minimize the maximum job completion time. It is showed that this problem is NP-hard. And a pseudo-polynomial time optimal algorithm is presented. A polynomial time approximation algorithm with worst-case ratio 2 is also presented.
基金Research partly supported by Chinese NSF grant 19731001 and National 973 Information Technology and High-Performance Software Program of China with grant No.G1998030401.The first author gratefully acknowledges the support of K.C.Wong Education Foundat
文摘Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. In many interesting cases, the algorithm performs better than the algorithms of Ye and of Halperin and Zwick. The main tool used to obtain this result is semidefinite programming.
基金supported in part by Hong Kong General Research Fund(No.CityU143711)Zhening Li was supported in part by Natural Science Foundation of Shanghai(No.12ZR1410100)+1 种基金Ph.D.Programs Foundation of Chinese Ministry of Education(No.20123108120002)Shuzhong Zhang was supported in part by U.S.National Science Foundation(No.CMMI-1161242).
文摘In this paper,we consider approximation algorithms for optimizing a generic multivariate polynomial function in discrete(typically binary)variables.Such models have natural applications in graph theory,neural networks,error-correcting codes,among many others.In particular,we focus on three types of optimization models:(1)maximizing a homogeneous polynomial function in binary variables;(2)maximizing a homogeneous polynomial function in binary variables,mixed with variables under spherical constraints;(3)maximizing an inhomogeneous polynomial function in binary variables.We propose polynomial-time randomized approximation algorithms for such polynomial optimizationmodels,and establish the approximation ratios(or relative approximation ratios whenever appropriate)for the proposed algorithms.Some examples of applications for these models and algorithms are discussed as well.
基金supported by the project of Central University Basic Research Fund(HEUCF150903)the project of the major research task,institute of Policy and Management,Chinese Academy of Sciences(Y201181z01)the National Natural Science Foundation of China(71273072)
文摘Abstract We study the fleet size and mix vehicle routing problem with constraints on the capacity of each vehicle. The objective is to minimize the total cost including fixed utilization cost of vehicles and traveling cost by vehicles. We give differential approximation algorithms for the fleet size and mix vehicle routing problem （FSMVRP） with two kinds of vehicles, the capacities of which are respectively nlk and n2k, n2 〉 nl ≥ 1, k ≥ 1. Using existing theories for vehicle routing problems and feature of the algorithms represented in the paper, we also prove that the algorithms give（1-6n＋3/（n＋1）2k＋n＋1）differential approximation ratio for （k, nk） VRP, n 〉 1and （1-6n2＋3n/n1k＋n2k）2k）differential approximation ratio for （nlk, n2k）VRP, n2 〉 nl 〉 1.
基金the National Natural Science Foundation of China (Nos.69873027, 60073042).
文摘The paper briefly reviews NP-hard optimization problems and their inapproximability. The hardness of solving CLIQUE problem is specifically dis- cussed. A dynamic-programming algorithm and its improved version for CLIQUE are reviewed and some additional analysis is presented. The analysis implies that the improved algorithm, HEWN (hierarchical edge-weighted network), only provides a heuristic or useful method, but cannot be called a polynomial algorithm.
