Approximation algorithms for combinatorial fractional programming problems

We are concerned with a combinatorial optimization problem which has the ratio of two linear functions as the objective function. This type of problems can be solved by an algorithm that uses an auxiliary problem with a parametrized linear objective function. Because of its combinatorial nature, however, it is often difficult to solve the auxiliary problem exactly. In this paper, we propose an algorithm which assumes that the auxiliary problems are solved only approximately, and prove that it gives an approximate solution to the original problem, of which the accuracy is at least as good as that of approximate solutions to the auxiliary problems. It is also shown that the time complexity is bounded by the square of the computation time of the approximate algorithm for the auxiliary problem. As an example of the proposed algorithm, we present a fully polynomial time approximation scheme for the fractional 0–1 knapsack problem.     

Models and algorithms for combinatorial optimization problems arising in railway applications

This is a summary of the author’s PhD thesis supervised by Alberto Caprara and Paolo Toth and defended on 29 May 2007 at the Università di Bologna. The thesis is written in English and is available from the author upon request. This work deals with Railway Optimization, and in particular it focuses on the Train Timetabling Problem (in the basic version on a corridor and in the extension to a railway network), and on the Train Unit Assignment Problem. Integer Linear Programming (ILP) formulations are proposed for both problems, and their continuous and Lagrangian relaxations are used to obtain optimal and heuristic solutions to real-world instances.      

Approximation algorithms for nonnegative polynomial optimization problems over unit spheres

We consider approximation algorithms for nonnegative polynomial optimization problems over unit spheres. These optimization problems have wide applications e.g., in signal and image processing, high order statistics, and computer vision. Since these problems are NP-hard, we are interested in studying on approximation algorithms. In particular, we propose some polynomial-time approximation algorithms with new approximation bounds. In addition, based on these approximation algorithms, some efficient algorithms are presented and numerical results are reported to show the efficiency of our proposed algorithms.     

Approximation algorithms for graph approximation problems

Several versions of the graph approximation problem are under study. Approximation algorithms for these problems are proposed, and performance guarantees of the algorithms are obtained. In particular, it is shown that the problem of approximation by graphs with a bounded number of connected components belongs to the class APX.     

Approximation algorithms for Hamming clustering problems

We study Hamming versions of two classical clustering problems. The Hamming radius p-clustering problem (HRC) for a set S of k binary strings, each of length n, is to find p binary strings of length n that minimize the maximum Hamming distance between a string in S and the closest of the p strings; this minimum value is termed the p-radius of S and is denoted by . The related Hamming diameter p-clustering problem (HDC) is to split S into p groups so that the maximum of the Hamming group diameters is minimized; this latter value is called the p-diameter of S.We provide an integer programming formulation of HRC which yields exact solutions in polynomial time whenever k is constant. We also observe that HDC admits straightforward polynomial-time solutions when k=O(logn) and p=O(1), or when p=2. Next, by reduction from the corresponding geometric p-clustering problems in the plane under the L₁ metric, we show that neither HRC nor HDC can be approximated within any constant factor smaller than two unless P=NP. We also prove that for any >0 it is NP-hard to split S into at most pk^1/7− clusters whose Hamming diameter does not exceed the p-diameter, and that solving HDC exactly is an NP-complete problem already for p=3. Furthermore, we note that by adapting Gonzalez' farthest-point clustering algorithm [T. Gonzalez, Theoret. Comput. Sci. 38 (1985) 293–306], HRC and HDC can be approximated within a factor of two in time O(pkn). Next, we describe a 2^O(p/)k^O(p/)n²-time (1+)-approximation algorithm for HRC. In particular, it runs in polynomial time when p=O(1) and =O(log(k+n)). Finally, we show how to find in

Full-size image

time a set L of O(plogk) strings of length n such that for each string in S there is at least one string in L within distance (1+), for any constant 0<<1.     

Knapsack problems with sigmoid utilities: Approximation algorithms via hybrid optimization

We study a class of non-convex optimization problems involving sigmoid functions. We show that sigmoid functions impart a combinatorial element to the optimization variables and make the global optimization computationally hard. We formulate versions of the knapsack problem, the generalized assignment problem and the bin-packing problem with sigmoid utilities. We merge approximation algorithms from discrete optimization with algorithms from continuous optimization to develop approximation algorithms for these NP-hard problems with sigmoid utilities.     

Approximation algorithms for problems in scheduling with set-ups

In this paper, we present new approximation results for the offline problem of single machine scheduling with sequence-independent set-ups and item availability, where the jobs to be scheduled are independent (i.e., have no precedence constraints) and have a common release time.We present polynomial-time approximation algorithms for two versions of this problem. In the first version, the input includes a weight for each job, and the goal is to minimize the total weighted completion time. On any input, our algorithm produces a schedule whose total weighted completion time is within a factor 2 of optimal for that input.In the second version, the input includes a due date for each job, and the goal is to minimize the maximum lateness of any job. On any input, our algorithm produces a schedule with the following performance guarantee: the maximum lateness of a job is at most the maximum lateness of the optimal schedule on a machine that runs at half the speed of our machine.     

Approximation algorithms for art gallery problems in polygons

In this paper, we present approximation algorithms for minimum vertex and edge guard problems for polygons with or without holes with a total of n vertices. For simple polygons, approximation algorithms for both problems run in O(n⁴) time and yield solutions that can be at most O(logn) times the optimal solution. For polygons with holes, approximation algorithms for both problems give the same approximation ratio of O(logn), but the running time of the algorithms increases by a factor of n to O(n⁵).     

Performance guarantees of greedy algorithms for the problems on hereditary systems

Under study are the problems of maximization and minimization of additive functions on hereditary systems which generalize many computationally hard combinatorial optimization problems. A performance guarantee of the greedy algorithm is proven in terms of the parameters of a feasible set and the objective function of the maximization problem. This bound improves the well-known Jenkyns—Korte—Hausmann bound. An analogous result is obtained for the minimization problem of an additive function on a hereditary system.     

Bi-criteria optimization problems for decision rules

We consider bi-criteria optimization problems for decision rules and rule systems relative to length and coverage. We study decision tables with many-valued decisions in which each row is associated with a set of decisions as well as single-valued decisions where each row has a single decision. Short rules are more understandable; rules covering more rows are more general. Both of these problems—minimization of length and maximization of coverage of rules are NP-hard. We create dynamic programming algorithms which can find the minimum length and the maximum coverage of rules, and can construct the set of Pareto optimal points for the corresponding bi-criteria optimization problem. This approach is applicable for medium-sized decision tables. However, the considered approach allows us to evaluate the quality of various heuristics for decision rule construction which are applicable for relatively big datasets. We can evaluate these heuristics from the point of view of (i) single-criterion—we can compare the length or coverage of rules constructed by heuristics; and (ii) bi-criteria—we can measure the distance of a point (length, coverage) corresponding to a heuristic from the set of Pareto optimal points. The presented results show that the best heuristics from the point of view of bi-criteria optimization are not always the best ones from the point of view of single-criterion optimization.     

Approximation algorithms for indefinite complex quadratic maximization problems

In this paper,we consider the following indefinite complex quadratic maximization problem: maximize zHQz,subject to zk ∈ C and zkm = 1,k = 1,...,n,where Q is a Hermitian matrix with trQ = 0,z ∈ Cn is the decision vector,and m 3.An (1/log n) approximation algorithm is presented for such problem.Furthermore,we consider the above problem where the objective matrix Q is in bilinear form,in which case a 0.7118 cos mπ 2approximation algorithm can be constructed.In the context of quadratic optimization,various extensions and connections of the model are discussed.     

Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems

Semidefinite relaxations of certain combinatorial optimization problems lead to approximation algorithms with performance guarantees. For large-scale problems, it may not be computationally feasible to solve the semidefinite relaxations to optimality. In this paper, we investigate the effect on the performance guarantees of an approximate solution to the semidefinite relaxation for MaxCut, Max2Sat, and Max3Sat. We show that it is possible to make simple modifications to the approximate solutions and obtain performance guarantees that depend linearly on the most negative eigenvalue of the approximate solution, the size of the problem, and the duality gap. In every case, we recover the original performance guarantees in the limit as the solution approaches the optimal solution to the semidefinite relaxation.     

Approximation algorithms for group prize-collecting and location-routing problems

In this paper we develop approximation algorithms for generalizations of the following three known combinatorial optimization problems, the Prize-Collecting Steiner Tree problem, the Prize-Collecting Travelling Salesman Problem and a Location-Routing problem.Given a graph G=(V,E) on n vertices and a length function on its edges, in the grouped versions of the above mentioned problems we assume that V is partitioned into k+1 groups, {V₀,V₁,…,V_k}, with a penalty function on the groups. In the Group Prize-Collecting Steiner Tree problem the aim is to find S, a collection of groups of V and a tree spanning the rest of the groups not in S, so as to minimize the sum of the costs of the edges in the tree and the costs of the groups in S. The Group Prize-Collecting Travelling Salesman Problem, is defined analogously. In the Group Location-Routing problem the customer vertices are partitioned into groups and one has to select simultaneously a subset of depots to be opened and a collection of tours that covers the customer groups. The goal is to minimize the costs of the tours plus the fixed costs of the opened depots. We give a -approximation algorithm for each of the three problems, where I is the cardinality of the largest group.     

Trajectory-following algorithms for min-max optimization problems

In this paper, we consider a class of nonlinear minimum-maximum optimization problems subject to boundedness constraints on the decision vectors. Three algorithms are developed for finding the min-max point using the concept of solving an associated dynamical system. In the first and third algorithms, solutions are obtained by solving systems of differential equations. The second algorithm is a discrete version of the first algorithm. The trajectories generated by the first and second algorithms may move inside or on the boundary of the constraint set, while the third algorithm ensures that any trajectory that begins inside the constraint region remains in its interior. Sufficient conditions for global convergence of the two algorithms are also established. For illustration, four numerical examples are solved.This work was partially supported by a research grant from the Australian Research Committee.     

Metaheuristic algorithms for combinatorial optimization problems

We present the main results in the author’s Ph.D. thesis (Iori 2004), defended at the University of Bologna in April 2004 and supervised by S. Martello. The thesis is written in English and is available from the author upon request. It proposes exact and metaheuristic algorithms for solving some relevant combinatorial optimization problems, with particular emphasis on scheduling, two-dimensional cutting and packing and capacitated vehicle routing. The performance of each algorithm is tested through extensive computational experiments and comparison with other approaches in the literature.Received: 21 September 2004, AMS classification: 90-08, 90C27, 90C59     

Approximation algorithms for homogeneous polynomial optimization with quadratic constraints

In this paper, we consider approximation algorithms for optimizing a generic multi-variate homogeneous polynomial function, subject to homogeneous quadratic constraints. Such optimization models have wide applications, e.g., in signal processing, magnetic resonance imaging (MRI), data training, approximation theory, and portfolio selection. Since polynomial functions are non-convex, the problems under consideration are all NP-hard in general. In this paper we shall focus on polynomial-time approximation algorithms. In particular, we first study optimization of a multi-linear tensor function over the Cartesian product of spheres. We shall propose approximation algorithms for such problem and derive worst-case performance ratios, which are shown to be dependent only on the dimensions of the model. The methods are then extended to optimize a generic multi-variate homogeneous polynomial function with spherical constraint. Likewise, approximation algorithms are proposed with provable approximation performance ratios. Furthermore, the constraint set is relaxed to be an intersection of co-centered ellipsoids; namely, we consider maximization of a homogeneous polynomial over the intersection of ellipsoids centered at the origin, and propose polynomial-time approximation algorithms with provable worst-case performance ratios. Numerical results are reported, illustrating the effectiveness of the approximation algorithms studied.     

Convergence of algorithms for perturbed optimization problems

Infinite-dimensional optimization problems occur in various applications such as optimal control problems and parameter identification problems. If these problems are solved numerically the methods require a discretization which can be viewed as a perturbation of the data of the optimization problem. In this case the expected convergence behavior of the numerical method used to solve the problem does not only depend on the discretized problem but also on the original one. Algorithms which are analyzed include the gradient projection method, conditional gradient method, Newton's method and quasi-Newton methods for unconstrained and constrained problems with simple constraints.     

Approximation algorithms for UET scheduling problems with exact delays

In this paper we consider coupled-task single-machine and two-machine flow shop scheduling problems with exact delays, unit processing times, and the makespan as an objective function. The main results of the paper are fast 7/4- and 3/2-approximation algorithms for solving the single- and two-machine problems, respectively.     

Approximation algorithms for multiple terminal, Hamiltonian path problems

This article presents a new 2-approximation algorithm for a multiple depot, multiple terminal, Hamiltonian path problem when the costs satisfy the triangle inequality. For the case where all the salesmen start from the same depot, we present another algorithm with an approximation ratio of \frac53{\frac{5}{3}}. These results generalize the approximation algorithms currently available for the single depot, single terminal Hamiltonian path problem.