Approximating the maximum vertex/edge weighted clique using local search

This paper extends the recently introduced Phased Local Search (PLS) algorithm to more difficult maximum clique problems and also adapts the algorithm to handle maximum vertex/edge weighted clique instances. PLS is a stochastic reactive dynamic local search algorithm that interleaves sub-algorithms which alternate between sequences of iterative improvement, during which suitable vertices are added to the current sub-graph, and plateau search, where vertices of the current sub-graph are swapped with vertices not contained in the current sub-graph. These sub-algorithms differ in firstly their vertex selection techniques in that selection can be solely based on randomly selecting a vertex, randomly selecting within highest vertex degree, or random selecting within vertex penalties that are dynamically adjusted during the search. Secondly, the perturbation mechanism used to overcome search stagnation differs between the sub-algorithms. PLS has no problem instance dependent parameters and achieves state-of-the-art performance for maximum clique and maximum vertex/edge weighted clique problems over a large range of the commonly used DIMACS benchmark instances.     

Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers

This paper extends the recently introduced Phased Local Search (PLS) maximum clique algorithm to unweighted/weighted maximum independent set and minimum vertex cover problems. PLS is a stochastic reactive dynamic local search algorithm that interleaves sub-algorithms which alternate between sequences of iterative improvement, during which suitable vertices are added to the current sub-graph, and plateau search, during which vertices of the current sub-graph are swapped with vertices not contained in the current sub-graph. These sub-algorithms differ in their vertex selection techniques and also in the perturbation mechanism used to overcome search stagnation. PLS has no problem instance dependent parameters and achieves state-of-the-art performance over a large range of the commonly used DIMACS and other benchmark instances.     

Foolproof eternal domination in the all-guards move model

The eternal domination problem requires a graph be protected against an infinitely long sequence of attacks at vertices, by guards located at vertices, with the requirement that the configuration of guards induces a dominating set at all times. An attack is defended by sending a guard from a neighboring vertex to the attacked vertex. We allow all guards to move to neighboring vertices in response to an attack, but allow the attacked vertex to choose which neighboring guard moves to the attacked vertex. This is the all-guards move version of the ??foolproof?? eternal domination problem that has been previously studied. We present some results and conjectures on this problem.     

Perturbations for Delaunay and weighted Delaunay 3D triangulations

The Delaunay triangulation and the weighted Delaunay triangulation are not uniquely defined when the input set is degenerate. We present a new symbolic perturbation that allows to always define these triangulations in a unique way, as soon as the points are not all coplanar. No flat tetrahedron exists in the defined triangulation. The perturbation scheme is easy to code. It is implemented in cgal, and guarantees that both vertex insertion and vertex removal are fully robust.     

A note on degeneracy in linear programming

We show that the problem of exiting a degenerate vertex is as hard as the general linear programming problem. More precisely, every linear programming problem can easily be reduced to one where the second best vertex (which is highly degenerate) is already given. So, to solve the latter, it is sufficient to exit that vertex in a direction that improves the objective function value.     

Continuous Subsonic-Sonic Flows in a Convergent Nozzle

This paper concerns continuous subsonic-sonic potential flows in a two-dimensional convergent nozzle. It is shown that for a given nozzle which is a perturbation of a straight one, a given point on its wall where the curvature is zero, and a given inlet which is a perturbation of an arc centered at the vertex, there exists uniquely a continuous subsonic-sonic flow whose velocity vector is along the normal direction at the inlet and the sonic curve, which satisfies the slip conditions on the nozzle walls and whose sonic curve intersects the upper wall at the given point. Furthermore, the sonic curve of this flow is a free boundary, where the flow is singular in the sense that the speed is only C^1/2 Hölder continuous and the acceleration blows up. The perturbation problem is solved in the potential plane, where the flow is governed by a free boundary problem of a degenerate elliptic equation with two free boundaries and two nonlocal boundary conditions, and the equation is degenerate at one free boundary.     

Weakly redundant constraints and their impact on postoptimal analyses in LP

Suppose that in a mathematical programming problem with a smooth objective function the constraints set is formed by linear inequalities. Then, as is well known, it is possible to determine redundant constraints before the optimization procedure starts. If some of the vertices of the convex polyhedron defined by the linear constraints are degenerate, the known redundancy-determining procedures may fail. Based on the recently developed theory of degeneracy graphs (DG's for short) a procedure is suggested how to proceed in degenerate cases. Weakly redundant constraints which cause degeneracy do have some impact on sensitivity analyses with respect oo the RHS or objective function coefficients. Using again the theory of DG's this impact is analysed. Also procedures are suggested how to perform sensitivity analyses when the degeneracy of the optimal vertex is not caused only by weakly redundant constraints. Small numerical examples are used for illustration.     

Graphs with equal eternal vertex cover and eternal domination numbers

Mobile guards on the vertices of a graph are used to defend it against an infinite sequence of attacks on either its vertices or its edges. If attacks occur at vertices, this is known at the eternal domination problem. If attacks occur at edges, this is known as the eternal vertex cover problem. We focus on the model in which all guards can move to neighboring vertices in response to an attack. Motivated by the question of which graphs have equal eternal vertex cover and eternal domination numbers, a number of results are presented; one of the main results of the paper is that the eternal vertex cover number is greater than the eternal domination number (in the all-guards move model) in all graphs of minimum degree at least two.     

Vertex covers and eternal dominating sets

The eternal domination problem requires a graph to be protected against an infinitely long sequence of attacks on vertices by guards located at vertices, the configuration of guards inducing a dominating set at all times. An attack at a vertex with no guard is defended by sending a guard from a neighboring vertex to the attacked vertex. We allow any number of guards to move to neighboring vertices at the same time in response to an attack. We compare the eternal domination number with the vertex cover number of a graph. One of our main results is that the eternal domination number is less than the vertex cover number of any graph of minimum degree at least two having girth at least nine.     

An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem

Given an undirected graph and a weighting function defined on the vertex set, the minimum weight vertex cover problem is to find a vertex subset whose total weight is minimum subject to the premise that the selected vertices cover all edges in the graph. In this paper, we introduce a meta-heuristic based upon the Ant Colony Optimization (ACO) approach, to find approximate solutions to the minimum weight vertex cover problem. In the literature, the ACO approach has been successfully applied to several well-known combinatorial optimization problems whose solutions might be in the form of paths on the associated graphs. A solution to the minimum weight vertex cover problem however needs not to constitute a path. The ACO algorithm proposed in this paper incorporates several new features so as to select vertices out of the vertex set whereas the total weight can be minimized as much as possible. Computational experiments are designed and conducted to study the performance of our proposed approach. Numerical results evince that the ACO algorithm demonstrates significant effectiveness and robustness in solving the minimum weight vertex cover problem.     

A dual approach to primal degeneracy

The Revised Primal Simplex algorithm, in its simplest form, has no defence against degeneracy. Various forms of the perturbation method are usually effective, but most offer no guarantee of avoiding all degeneracy, and can lead to numerical difficulties. This paper presents a method that avoids cycling and circling by taking a dual approach.The degenerate subproblem consists of all the original variables, but only the degenerate transformed constraints. The current primal objective, which may be mixed, is used. This subproblem may be solved using the dual simplex algorithm, starting from the current dual infeasible solution, and with a zero dual objective. If the dual algorithm terminates optimally then the whole problem is optimal (subject to primal feasibility). Otherwise the final solution provides a non-basic direction which improves the value of the mixed primal objective and moves away from the degenerate vertex. A purification algorithm then renders the solution basic and further improves the mixed objective.     

The cover pebbling number of graphs

A pebbling move on a graph consists of taking two pebbles off of one vertex and placing one pebble on an adjacent vertex. In the traditional pebbling problem we try to reach a specified vertex of the graph by a sequence of pebbling moves. In this paper we investigate the case when every vertex of the graph must end up with at least one pebble after a series of pebbling moves. The cover pebbling number of a graph is the minimum number of pebbles such that however the pebbles are initially placed on the vertices of the graph we can eventually put a pebble on every vertex simultaneously. We find the cover pebbling numbers of trees and some other graphs. We also consider the more general problem where (possibly different) given numbers of pebbles are required for the vertices.     

Finding all efficient extreme points for multiple objective linear programs

In this paper we develop a method for finding all efficient extreme points for multiple objective linear programs. Simple characterizations of the efficiency of an edge incident to a nondegenerate or a degenerate efficient vertex are given. These characterizations form the basis of an algorithm for enumerating all efficient vertices. The algorithm appears to have definite computational advantages over other methods. Some illustrative examples are included.     

Allocating Vertex π-Guards in Simple Polygons via Pseudo-Triangulations

We use the concept of pointed pseudo-triangulations to establish new upper and lower bounds on a well known problem from the area of art galleries: What is the worst case optimal number of vertex π-guards that collectively monitor a simple polygon with n vertices? Our results are as follows: (1) Any simple polygon with n vertices can be monitored by at most \lfloor n/2 \rfloor general vertex π-guards. This bound is tight up to an additive constant of 1. (2) Any simple polygon with n vertices, k of which are convex, can be monitored by at most \lfloor (2n – k)/3 \rfloor edge-aligned vertexπ-guards. This is the first non-trivial upper bound for this problem and it is tight for the worst case families of polygons known so far.     

A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees

Given an undirected graph with nonnegative edge lengths and nonnegative vertex weights, the routing requirement of a pair of vertices is assumed to be the product of their weights. The routing cost for a pair of vertices on a given spanning tree is defined as the length of the path between them multiplied by their routing requirement. The optimal product-requirement communication spanning tree is the spanning tree with minimum total routing cost summed over all pairs of vertices. This problem arises in network design and computational biology. For the special case that all vertex weights are identical, it has been shown that the problem is NP-hard and that there is a polynomial time approximation scheme for it. In this paper we show that the generalized problem also admits a polynomial time approximation scheme.     

Random walks on graphs

In this paper the following Markov chains are considered: the state space is the set of vertices of a connected graph, and for each vertex the transition is always to an adjacent vertex, such that each of the adjacent vertices has the same probability. Detailed results are given on the expectation of recurrence times, of first-entrance times, and of symmetrized first-entrance times (called commuting times). The problem of characterizing all connected graphs for which the commuting time is constant over all pairs of adjacent vertices is solved almost completely.     

On degenerate surface patches

A local construction of aGC ¹ interpolating surface to given scattered data in ³ can give rise to degenerate Bernstein-Bézier patches. This means that the parametrization at vertices is not regular in the sense that the length of the tangent vector to any curve passing through a vertex is zero at that vertex. This implies that the curvature of these curves tends to infinity whenever one approaches a vertex. This fact seems not to have a negative influence on the shape of the surface.     

Ranking of vertices in the linear fractional programming problem

In this paper the problem of ranking vertices in the linear fractional programming problem is considered. It is shown that a class of vertex ranking algorithms for the linear programming problem can be used with only minor modifications.     

Pseudosimilar vertices in a graph

Dissimilar vertices whose removal leaves isomorphic subgraphs are called pseudosimilar. We construct infinite families of graphs having identity automorphism group, yet every vertex is pseudosimilar to some other vertex. Potential impact on the Reconstruction Conjecture is considered. We also construct, for each n, graphs containing a subset of n vertices which are mutually pseudosimilar. the analogous problem for mutually pseudosimilar edges is introduced.     

A criterion for the adjacency of vertices of polytopes generated by subsets of symmetric groups

We propose a characterization of the adjacency of vertices in the class of permutation polytopes generated by arbitrary subsets of symmetric groups. In particular, this class contains polytopes for the well-known classical problems, such as the assignment problem, 2-and 3-combinations, the traveling salesman problem and their various modifications. Up to now, the problem of vertex adjacency has been studied for a single polytope only. In the present paper, we obtain, for general permutation polytopes, necessary and sufficient conditions that guarantee that two given vertices are adjacent (or not) to each other. The conditions are formulated in terms of permutations and of the solvability of certain special systems of linear equations. The presently known adjacency criteria for vertices of polytopes for the assignment problem are simple corollaries of our conditions. The latter allow us to develop a general algorithmic scheme for recognizing vertex adjacency of a general permutation polytope and estimate its complexity.