An edge-reduction algorithm for the vertex cover problem

An approximation algorithm for the vertex cover problem is proposed with performance ratio on special graphs. On an arbitrary graph, the algorithm guarantees a vertex cover S₁ such that where S^∗ is an optimal cover and ξ is an error bound identified.     

Minimum vertex cover problem for coupled interdependent networks with cascading failures

This paper defines and analyzes a generalization of the classical minimum vertex cover problem to the case of two-layer interdependent networks with cascading node failures that can be caused by two common types of interdependence. Previous studies on interdependent networks mainly addressed the issues of cascading failures from a numerical simulations perspective, whereas this paper proposes an exact optimization-based approach for identifying a minimum-cardinality set of nodes, whose deletion would effectively disable both network layers through cascading failure mechanisms. We analyze the computational complexity and linear 0–1 formulations of the defined problems, as well as prove an LP approximation ratio result that generalizes the well-known 2-approximation for the classical minimum vertex cover problem. In addition, we introduce the concept of a “depth of cascade” (i.e., the maximum possible length of a sequence of cascading failures for a given interdependent network) and show that for any problem instance this parameter can be explicitly derived via a polynomial-time procedure.     

Minor‐order obstructions for the graphs of vertex cover 6

We provide for the first time, a complete list of forbidden minors (obstructions) for the family of graphs with vertex cover 6. This study shows how to limit both the search space of graphs and improve the efficiency of an obstruction checking algorithm when restricted to k–VERTEX COVER graph families. In particular, our upper bounds 2k + 1 (2k + 2) on the maximum number of vertices for connected (disconnected) obstructions are shown to be sharp for all k > 0. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 163–178, 2002     

A 2-approximation algorithm for the network substitution problem

The network substitution problem is to substitute an existing network for a new network so that to minimize the cost of exploiting the existing network during the period when the new network is being constructed. We show that this problem is NP-hard, and propose a 2-approximation algorithm for solving it.     

带惩罚的容错设施布局问题的近似算法

在带惩罚的容错设施布局问题中, 给定顾客集合、地址集合、以及每个顾客和各个地址之间的连接费用, 这里假设连接费用是可度量的. 每位顾客有各自的服务需求, 每个地址可以开设任意多个设施, 顾客可以被安排连接到某些地址的一些开设的设施上以满足其需求, 也可以被拒绝, 但这时要支付拒绝该顾客所带来的惩罚费用. 目标是确定哪些顾客的服务需求被拒绝并开设一些设施, 将未被拒绝的顾客连接到不同的开设设施上, 使得开设费用、连接费用和惩罚费用总和最小. 给出了带惩罚的容错设施布局问题的线性整数规划及其对偶规划, 进一步, 给出了基于其线性规划和对偶规划舍入的4-近似算法.     

A list heuristic for vertex cover

We analyze a list heuristic for the vertex cover problem that handles the vertices in a given static order based on the degree sequence. We prove an approximation ratio of at most for a nonincreasing degree sequence, and show that no ordering can achieve an approximation ratio of less than .     

An improved approximation algorithm for the partial Latin square extension problem

Previous work on the partial Latin square extension (PLSE) problem resulted in a 2-approximation algorithm based on the LP relaxation of a three-dimensional assignment IP formulation. We present an e/(e−1)-approximation algorithm that is based on the LP relaxation of a packing IP formulation of the PLSE problem.     

A new algorithm for the solution of the linear minimax approximation problem

This paper introduces an efficient approach to the solution of the linear mini-max approximation problem. The classical nonlinear minimax problem is cast into a linear formulation. The proposed optimization procedure consists of specifying first a feasible point belonging to the feasible boundary surface. Next, feasible directions of decreasing values of the objective function are determined. The algorithm proceeds iteratively and terminates when the absolute minimum value of the objective function is reached. The initial point May be selected arbitrarily or it May be optimally determined through a linear method to speed up algorithmic convergence. The algorithm was applied to a number of approximation problems and results were compared to those derived using the revised simplex method. The new algorithm is shown to speed up the problem solution by at least on order of magnitude.     

2-approximation algorithm for minmax absolute maximum lateness scheduling-location problem

The problem of minmax absolute scheduling-location is investigated on trees with interval edge length. Jobs are located at vertices and must travel to the machine. The goal is to find a machine location and simultaneously a schedule to minimize the maximum lateness in the worst-case. We derive a result that could reduce the robust versions to deterministic problems. An efficient algorithm is developed to solve special cases. A 2-approximation algorithm is proposed for the robust problem on the underlying tree.     

混合图上最小-最大圈覆盖问题的近似算法

考虑一个混合图上的最小-最大圈覆盖问题.给定一个正整数k和一个混合加权图G=(V E,A),这里V表示顶点集,E表示边集,A表示弧集.E中的每条边和A中的每条弧关联一个权重.问题的要求是确定k个环游,使得这k个环游能够经过A中的所有弧.目标是极小化最大环游的权重.该问题是运筹学和计算机科学中一个重要的组合优化问题,它和...     

A projection iterative algorithm for strong vector equilibrium problem

In this paper, iterative algorithm for strong vector equilibrium problem (SVEP) is studied. Firstly, an auxiliary problem for SVEP is introduced and the relationships between these two problems are discussed. Then, based on the auxiliary problem, a projection iterative algorithm for SVEP is proposed. Moreover, analysis of convergence of this iterative algorithm is investigated under suitable conditions of continuity and convexity. The main result obtained in this paper generalizes and improves the corresponding ones of Iusem and Sosa [Iusem AN, Sosa W. Iterative algorithms for equilibrium problems. Optimization. 2003;52(3):301–316.] and Cheng and Liu [Cheng B, Liu SY. An iterative algorithm for vector equilibrium problems. J. Lanzhou Univ. (Nat. Sci.). 2009;45(5):105–109.].     

A GRASP algorithm for the multi-criteria minimum spanning tree problem

This paper proposes a GRASP (Greedy Randomized Adaptive Search Procedure) algorithm for the multi-criteria minimum spanning tree problem, which is NP-hard. In this problem a vector of costs is defined for each edge of the graph and the problem is to find all Pareto optimal or efficient spanning trees (solutions). The algorithm is based on the optimization of different weighted utility functions. In each iteration, a weight vector is defined and a solution is built using a greedy randomized constructive procedure. The found solution is submitted to a local search trying to improve the value of the weighted utility function. We use a drop-and-add neighborhood where the spanning trees are represented by Prufer numbers. In order to find a variety of efficient solutions, we use different weight vectors, which are distributed uniformly on the Pareto frontier. The proposed algorithm is tested on problems with r=2 and 3 criteria. For non-complete graphs with n=10, 20 and 30 nodes, the performance of the algorithm is tested against a complete enumeration. For complete graphs with n=20, 30 and 50 nodes the performance of the algorithm is tested using two types of weighted utility functions. The algorithm is also compared with the multi-criteria version of the Kruskal’s algorithm, which generates supported efficient solutions. This work was funded by the Municipal Town Hall of Campos dos Goytacazes city. The used computer was acquired with resource of CNPq.     

A linear-time approximation algorithm for the weighted vertex cover problem

A linear time approximation algorithm for the weighted set-covering problem is presented. For the special case of the weighted vertex cover problem it produces a solution of weight which is at most twice the weight of an optimal solution.     

A new heuristic algorithm solving the linear ordering problem

The linear ordering problem is an NP-hard combinatorial problem with a large number of applications. Contrary to another very popular problem from the same category, the traveling salesman problem, relatively little space in the literature has been devoted to the linear ordering problem so far. This is particularly true for the question of developing good heuristic algorithms solving this problem.In the paper we propose a new heuristic algorithm solving the linear ordering problem. In this algorithm we made use of the sorting through insertion pattern as well as of the operation of permutation reversal. The surprisingly positive effect of the reversal operation, justified in part theoretically and confirmed in computational examples, seems to be the result of a unique property of the problem, called in the paper the symmetry of the linear ordering problem. This property consists in the fact that if a given permutation is an optimal solution of the problem with the criterion function being maximized, then the reversed permutation is a solution of the problem with the same criterion function being minimized.     

A .699-approximation algorithm for Max-Bisection

We present a .699-approximation algorithm for Max-Bisection, i.e., partitioning the nodes of a weighted graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. This is an improved result from the .651-approximation algorithm of Frieze and Jerrum and the semidefinite programming relaxation of Goemans and Williamson. Received: October 1999 / Accepted: July 2000?Published online January 17, 2001     

An iterative algorithm for a Cauchy problem in eddy-current modelling

We consider a linear steady-state eddy-current problem for a magnetic field in a bounded domain. The boundary consists of two parts: reachable with prescribed Cauchy data and unreachable with no data on it. We design an iterative (Landweber type) algorithm for solution of this problem. At each iteration step two auxiliary mixed well-posed boundary value problems are solved. The analysis of temporary problems is performed in suitable function spaces. This creates the basis for the convergence argument. The theoretical results are supported with numerical experiments.