APPOXIMATION 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 unirected 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.     

A note on maximizing a submodular set function subject to a knapsack constraint

In this paper, we obtain an (1−e⁻¹)-approximation algorithm for maximizing a nondecreasing submodular set function subject to a knapsack constraint. This algorithm requires O(n⁵) function value computations.     

Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems

This paper deals with a single allocation problem in hub-and-spoke networks. We present a simple deterministic 3-approximation algorithm and randomized 2-approximation algorithm based on a linear relaxation problem and a randomized rounding procedure. We handle the case where the number of hubs is three, which is known to be NP-hard, and present a (5/4)-approximation algorithm.The single allocation problem includes a special class of the metric labeling problem, defined by introducing an assumption that both objects and labels are embedded in a common metric space. Under this assumption, we can apply our algorithms to the metric labeling problem without losing theoretical approximation ratios. As a byproduct, we also obtain a (4/3)-approximation algorithm for an ordinary metric labeling problem with three labels.     

Time-dependent optimization of a multi-item uncertain supply chain network: A hybrid approximation algorithm

We consider the uncertain least cost shipping problem. The input is a multi-item supply chain network with time-evolving uncertain costs and capacities. Exploiting the operational law of uncertainty theory, a mathematical model of the problem is established and the indeterminacy factors are tackled. We use the scaling idea together with transformation approach and uncertainty programming to develop a hybrid algorithm to optimize and obtain the uncertainty distribution of the total shipping cost. We analyze the practical performance of the algorithm and present an illustrative example.     

SEMI-DEFINITE RELAXATION ALGORITHM FOR SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES

The authors present a semi-definite relaxation algorithm for the scheduling problem with controllable times on a single machine. Their approach shows how to relate this problem with the maximum vertex-cover problem with kernel constraints (MKVC). The established relationship enables to transfer the approximate solutions of MKVC into the approximate solutions for the scheduling problem. Then, they show how to obtain an integer approximate solution for MKVC based on the semi-definite relaxation and randomized rounding technique.     

Polyhedral approximations of strictly convex compacta

We consider polyhedral approximations of strictly convex compacta in finite-dimensional Euclidean spaces (such compacta are also uniformly convex). We obtain the best possible estimates for errors of considered approximations in the Hausdorff metric. We also obtain new estimates of an approximate algorithm for finding the convex hulls.     

On a Minimum Linear Classification Problem

We study the following linear classification problem in signal processing: Given a set Bof n black point and a set W of m white points in the plane (m = O(n)), compute a minimum number of lines L such that in the arrangement of L each face contain points with the same color (i.e., either all black points or all white points). We call this the Minimum Linear Classification (MLC) problem. We prove that MLC is NP-complete by a reduction from the Minimum Line Fitting (MLF) problem; moreover, a C-approximation to MLC implies a C-approximation to the MLF problem. Nevertheless, we obtain an O(log n)-factor algorithm for MLC and we also obtain an O(log Z)-factor algorithm for MLC where Z is the minimum number of disjoint axis-parallel black/white rectangles covering B and W.     

On a Minimum Linear Classification Problem

We study the following linear classification problem in signal processing: Given a set B of n black point and a set W of m white points in the plane (m=O(n)), compute a minimum number of lines L such that in the arrangement of L each face contain points with the same color (i.e., either all black points or all white points). We call this the Minimum Linear Classification (MLC) problem. We prove that MLC is NP-complete by a reduction from the Minimum Line Fitting (MLF) problem; moreover, a C-approximation to Minimum Linear Classification implies a C-approximation to the Minimum Line Fitting problem. Nevertheless, we obtain an O(log _n )-factor algorithm for MLC and we also obtain an O(log _Z)-factor algorithm for MLC where Z is the minimum number of disjoint axis-parallel black/white rectangles covering B and W.     

Approximation results for a min-max location-routing problem

This paper studies a min-max location-routing problem, which aims to determine both the home depots and the tours for a set of vehicles to service all the customers in a given weighted graph, so that the maximum working time of the vehicles is minimized. The min-max objective is motivated by the needs of balancing or fairness in vehicle routing applications. We have proved that unless NP=P, it is impossible for the problem to have an approximation algorithm that achieves an approximation ratio of less than 4/3. Thus, we have developed the first constant ratio approximation algorithm for the problem. Moreover, we have developed new approximation algorithms for several variants, which improve the existing best approximation ratios in the previous literature.     

Independent sets in bounded-degree hypergraphs

In this paper we analyze several approaches to the Maximum Independent Set (MIS) problem in hypergraphs with degree bounded by a parameter Δ. Since independent sets in hypergraphs can be strong and weak, we denote by MIS (MSIS) the problem of finding a maximum weak (strong) independent set in hypergraphs, respectively. We propose a general technique that reduces the worst case analysis of certain algorithms on hypergraphs to their analysis on ordinary graphs. This technique allows us to show that the greedy algorithm for MIS that corresponds to the classical greedy set cover algorithm has a performance ratio of (Δ+1)/2. It also allows us to apply results on local search algorithms on graphs to obtain a (Δ+1)/2 approximation for the weighted MIS and (Δ+3)/5−? approximation for the unweighted case. We improve the bound in the weighted case to ⌈(Δ+1)/3⌉ using a simple partitioning algorithm. We also consider another natural greedy algorithm for MIS that adds vertices of minimum degree and achieves only a ratio of Δ−1, significantly worse than on ordinary graphs. For MSIS, we give two variations of the basic greedy algorithm and describe a family of hypergraphs where both algorithms approach the bound of Δ.     

Adaptive-Additive Multilevel Methods for Hypersingular Integral Equation

In this article we present the combined adaptive-additive multilevel methods for the Galerkin approximation of hypersingular integral equation on the interval o = ( m 1,1). We also derive an efficient and reliable a posteriori error estimate for the error between the exact solution u and the approximated multilevel solution $ \tilde u_ {\cal M} $ , measuring locally the quality of $ \tilde u_ {\cal M} $ . The algorithm is carefully designed to obtain minimal complexity. A limitation of our analysis approach is that the meshes must be assumed to be quasi-uniform.     

Multi-criteria TSP: Min and max combined

We present randomized approximation algorithms for multi-criteria traveling salesman problems (TSP), where some objective functions should be minimized while others should be maximized. For the symmetric multi-criteria TSP (STSP), we present an algorithm that computes (2/3,3+ε)-approximate Pareto curves. Here, the first parameter is the approximation ratio for the objectives that should be maximized, and the second parameter is the ratio for the objectives that should be minimized. For the asymmetric multi-criteria TSP (ATSP), we obtain an approximation performance of (1/2,log₂n+ε).     

Strong Stability of Queues with Multiple Vacation of the Server

Abstract

The main purpose of this article is to use the strong stability method to approximate the characteristics of the M/G/1//N queue with server vacation by those of the classical M/G/1//N queue, when the rate of the vacations is sufficiently small. This last queue is simpler and more exploitable in practice. For this, we proof the stability conditions and next obtain quantitative stability estimates with an exact computation of constants. From these theoretical results, we can develop an algorithm in order to check the conditions of approximation. These results of approximation have a great practical and economic interest in reliability systems and maintenance optimization policy, when we consider elements with constant failure rate.     

Constant approximation for fault-tolerant median problems via iterative rounding

In this paper, we study the fault-tolerant matroid median and fault-tolerant knapsack median problems. These two problems generalize many fundamental clustering and facility location problems, such as uniform fault-tolerant k-median, uniform fault-tolerant facility location, matroid median, knapsack median, etc. We present a versatile iterative rounding framework and obtain a unifying constant-factor approximation algorithm.     

有约束单向豪斯道夫最佳逼近的唯一性

本文研究单向豪斯道夫度量下的带约束条件的多项式最佳逼近问题，得到唯一性定理。     

An algorithm for determining the approximation orders of multivariate periodic spline spaces

We give an algorithm which computes the approximation order of spaces of periodic piece-wise polynomial functions, given the degree, the smoothness and tesselation. The algorithm consists of two steps. The first gives an upper bound and the second a lower bound on the approximation order. In all known cases the two bounds coincide.     

An approximation algorithm for a symmetric Generalized Multiple Depot, Multiple Travelling Salesman Problem

In this paper, we present an algorithm with an approximation factor of 2 for a Generalized, Multiple Depot, Multiple Travelling Salesman Problem (GMTSP) when the costs are symmetric and satisfy the triangle inequality. The algorithm requires finding a degree constrained minimum spanning tree which we compute using a Lagrangian relaxation.     

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.     

Performance analysis approximation in a queueing system of type M/G/1

In this work, we apply the strong stability method to obtain an estimate for the proximity of the performance measures in the M/G/1 queueing system to the same performance measures in the M/M/1 system under the assumption that the distributions of the service time are close and the arrival flows coincide. In addition to the proof of the stability fact for the perturbed M/M/1 queueing system, we obtain the inequalities of the stability. These results give with precision the error, on the queue size stationary distribution, due to the approximation. For this, we elaborate from the obtained theoretical results, the STR-STAB algorithm which we execute for a determined queueing system: M/Coxian − 2/1. The accuracy of the approach is evaluated by comparison with simulation results.