Simultaneous Approximation Ratios for Parallel Machine Scheduling Problems

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.

APPROXIMATION ALGORITHM FOR MAX-BISECTION PROBLEM WITH THE POSITIVE SEMIDEFINITE RELAXATION

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.

Approximation Algorithms for Discrete Polynomial Optimization

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.

ON APPROXIMATION OF MAX n/2-UNCUT PROBLEM

Using outward rotations, we obtain an approximation algorithm for MAXn/2-UNCUT problem, i.e., partitioning the vertices of a weighted graph into two blocks of equalcardinality such that the total weight of edges that do not cross the cut is maximized. In manyinteresting cases, the algorithm performs better than the algorithms of Ye and of Halperin andZwick. The main tool used to obtain this result is semidefinite programming.

Differential Approximation Algorithm of FSMVRP

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.

Approximation of dense-n/2-subgraph and table compression problems

We develop improved approximation algorithms for two NP-hard problems: the dense-n/2-subgraph and table compression.Based on SDP relaxation and advanced rounding techniques,we first propose 0. 5982 and 0. 5970-approximation algorithms respec- tively for the dense-n/2-subgraph problem (DSP) and the table compression problem (TCP). Then we improve these bounds to 0. 6243 and 0. 6708 respectively for DSP and TCP by adding triangle inequalities to strengthen the SDP relaxation.The results for TCP beat the 0. 5 bound of a simple greedy algorithm on this problem,and hence answer an open question of Anderson in an affirmative way.

First-order perturbation approximation for rock elastic moduli in transversely isotropic media

Seismic anisotropy is a relatively common seismic wave phenomenon in laminated sedimentary rocks such as shale and it can be used to investigate mechanical properties of such rocks and other geological materials. Young's modulus and Poisson's ratio are the most common mechanical properties determined in various rock engineering practices. Approximate and explicit equations are proposed for determining Young's modulus and Poisson's ratio in anisotropic rocks, in which the symmetry plane and symmetry axis of the anisotropy are derived from the constitutive equation of transversely isotropic rock. These equations are based on the media decomposition principle and seismic wave perturbation theory and their accuracy is tested on two sets of laboratory data. A strong correlation is found for Young's modulus in two principal directions and for Poisson's ratio along the symmetry plane. Further, there is an underprediction of Poisson's ratio along the symmetry axis, although the overall behavior follows the trend of the measured data. Tests on a real dataset show that it is necessary to account for anisotropy when characterizing rock mechanical properties of shale. The approximate equations can effectively estimate anisotropic Young's modulus and Poisson's ratio, both of which are critical rock mechanical data input for hydraulic fracturing engineering.

Hardness and Methods to Solve CLIQUE

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.

TO IMPROVE THE COMMUNICATION DELAY BY UPGRADING NODES IN A CONTINUOUS VERSION

In this paper, we consider a network communication delay improvement problem,which is to upgrade nodes in a network with minimum cost such that the communication delay betweenany two nodes of the network is below a pre-specific level. In the upgrading model, the improvementby upgrading one node is a continuous variable, and the cost incurred by such an upgrading is alinear function of the improvement. We show that achieving an approximation ratio βln(|V|) for theproblem is NP-hard for some constant β > 0 even if the underlying network is a bipartite graph. Butif the underlying network is restricted as a tree, we show that it can be solved in a stronglypolynomial time.