The Proportional Colouring Problem: Optimizing Buffers in Wireless Mesh Networks

In this paper, we consider a new edge colouring problem motivated by wireless mesh networks optimization: the proportional edge colouring problem. Given a graph G with positive weights associated to its edges, we want to find a proper edge colouring which assigns to each edge at least a proportion (given by its weight) of all the colours. If such colouring exists, we want to find one using the minimum number of colours. We proved that deciding if a weighted graph admits a proportional edge colouring is polynomial while determining its proportional edge chromatic number is NP-hard. We also give a lower and an upper bound that can be polynomially computed. We finally characterize some graphs and weighted graphs for which we can determine the proportional edge chromatic number.     

Cutting plane algorithms for solving a stochastic edge-partition problem

We consider the edge-partition problem, which is a graph theoretic problem arising in the design of Synchronous Optical Networks. The deterministic edge-partition problem considers an undirected graph with weighted edges, and simultaneously assigns nodes and edges to subgraphs such that each edge appears in exactly one subgraph, and such that no edge is assigned to a subgraph unless both of its incident nodes are also assigned to that subgraph. Additionally, there are limitations on the number of nodes and on the sum of edge weights that can be assigned to each subgraph. In this paper, we consider a stochastic version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from a finite set of alternatives, and then assign edges to subgraphs. We first prescribe a two-stage cutting plane approach with integer variables in both stages, and examine computational difficulties associated with the proposed cutting planes. As an alternative, we prescribe a hybrid integer programming/constraint programming algorithm capable of solving a suite of test instances within practical computational limits.     

An O(m log n) algorithm for the max + sum spanning tree problem

In a graph in which each edge has two weights, the max + sum spanning tree problem seeks a spanning tree that has the minimum value for the combined total of the maximum of one of the edge weights and the sum of the other weights among all the spanning trees in the graph. Exploiting an efficient data structure, an O(m log n) algorithm is presented for solving this problem. This improves the currently known bound of O(mn).     

Constant factor approximation for ATSP with two edge weights

We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was given recently by Svensson. This was accomplished by introducing an easier problem called Local-Connectivity ATSP and showing that a good solution to this problem can be used to obtain a constant factor approximation for ATSP. In this paper, we solve Local-Connectivity ATSP for two different edge weights. The solution is based on a flow decomposition theorem for solutions of the Held–Karp relaxation, which may be of independent interest.     

Approximation hardness of min-max tree covers

We prove the first inapproximability bounds to study approximation hardness for a min-max k-tree cover problem and its variants. The problem is to find a set of k trees to cover vertices of a given graph with metric edge weights, so as to minimize the maximum total edge weight of any of the k trees. Our technique can also be applied to improve inapproximability bounds for min-max problems that use other covering objectives, such as stars, paths, and tours.     

On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem

Considering an arbitrary undirected n-vertex graph with nonnegative edge weights, we seek to construct a spanning tree minimizing the sum over all vertices of the maximal weights of the incident edges. We find some particular cases of polynomial solvability and show that the minimal span whose edge weights lie in the closed interval [a, b] is a $\left( {2 - \frac{{2a}} {{a + b + 2b/(n - 2)}}} \right) $ -approximate solution, and the problem of constructing a 1.00048-approximate solution is NP-hard. We propose a heuristic polynomial algorithm and perform its a posteriori analysis.     

Matching interdiction

We introduce two interdiction problems involving matchings, one dealing with edge removals and the other dealing with vertex removals. Given is an undirected graph G with positive weights on its edges. In the edge interdiction problem, every edge of G has a positive cost and the task is to remove a subset of the edges constrained to a given budget, such that the weight of a maximum matching in the resulting graph is minimized. The vertex interdiction problem is analogous to the edge interdiction problem, with the difference that vertices instead of edges are removed. Hardness results are presented for both problems under various restrictions on the weights, interdiction costs and graph classes. Furthermore, we study the approximability of the edge and vertex interdiction problem on different graph classes. Several approximation-hardness results are presented as well as two constant-factor approximations, one of them based on iterative rounding. A pseudo-polynomial algorithm for solving the edge interdiction problem on graphs with bounded treewidth is proposed which can easily be adapted to the vertex interdiction problem. The algorithm presents a general framework to apply dynamic programming for solving a large class of problems in graphs with bounded treewidth. Additionally, we present a method to transform pseudo-polynomial algorithms for the edge interdiction problem into fully polynomial approximation schemes, using a scaling and rounding technique.     

Fuzzy minimum weight edge covering problem

Minimum weight edge covering problem, known as a classic problem in graph theory, is employed in many scientific and engineering applications. In the applications, the weight may denote cost, time, or opponent’s payoff, which can be vague in practice. This paper considers the edge covering problem under fuzzy environment, and formulates three models which are expected minimum weight edge cover model, α-minimum weight edge cover model, and the most minimum weight edge cover model. As an extension for the models, we respectively introduce the crisp equivalent of each model in the case that the weights are independent trapezoidal fuzzy variables. Due to the complexity of the problem, a hybrid intelligent algorithm is employed to solve the models, which can deal with the problem with any type of fuzzy weights. At last, some numerical experiments are given to show the application of the models and the robustness of the algorithm.     

Partial inverse maximum spanning tree in which weight can only be decreased under $$l_p$$-norm

The maximum or minimum spanning tree problem is a classical combinatorial optimization problem. In this paper, we consider the partial inverse maximum spanning tree problem in which the weight function can only be decreased. Given a graph, an acyclic edge set, and an edge weight function, the goal of this problem is to decrease weights as little as possible such that there exists with respect to function containing the given edge set. If the given edge set has at least two edges, we show that this problem is APX-Hard. If the given edge set contains only one edge, we present a polynomial time algorithm.     

2-Approximation algorithm for finding a clique with minimum weight of vertices and edges

The problem of finding a minimum clique (with respect to the total weight of its vertices and edges) of fixed size in a complete undirected weighted graph is considered along with some of its important subclasses. Approximability issues are analyzed. The inapproximability of the problem is proved for the general case. A 2-approximation efficient algorithm with time complexity O(n ²) is suggested for the cases when vertex weights are nonnegative and edge weights either satisfy the triangle inequality or are squared pairwise distances for some point configuration of Euclidean space.     

A polynomial algorithm for the multicriteria cent-dian location problem

Given a network with several weights per node and several lengths per edge, we address the problem of locating a facility on the network such that the convex combinations of the center and median objective functions are minimized. Since we consider several weights and several lengths, various objective functions should be minimized, and hence we have to solve a multicriteria cent-dian location problem. A polynomial algorithm to characterize the efficient location point set on the network is developed. Furthermore, this model can generalize other problems such as the multicriteria center problem and the multicriteria median problem. Computing time results on random planar networks considering different combinations of weights and lengths are reported, which strengthen the polynomial complexity of the procedure.     

A stabilized column generation scheme for the traveling salesman subtour problem

Given an undirected graph with edge costs and both revenues and weights on the vertices, the traveling salesman subtour problem is to find a subtour that includes a depot vertex, satisfies a knapsack constraint on the vertex weights, and that minimizes edge costs minus vertex revenues along the subtour.We propose a decomposition scheme for this problem. It is inspired by the classic side-constrained 1-tree formulation of the traveling salesman problem, and uses stabilized column generation for the solution of the linear programming relaxation. Further, this decomposition procedure is combined with the addition of variable upper bound (VUB) constraints, which improves the linear programming bound. Furthermore, we present a heuristic procedure for finding feasible subtours from solutions to the column generation problems. An extensive experimental analysis of the behavior of the computational scheme is presented.     

Edge searching weighted graphs

In traditional edge searching one tries to clean all of the edges in a graph employing the least number of searchers. It is assumed that each edge of the graph initially has a weight equal to one. In this paper we modify the problem and introduce the Weighted Edge Searching Problem by considering graphs with arbitrary positive integer weights assigned to its edges. We give bounds on the weighted search number in terms of related graph parameters including pathwidth. We characterize the graphs for which two searchers are sufficient to clear all edges. We show that for every weighted graph the minimum number of searchers needed for a not-necessarily-monotonic weighted edge search strategy is enough for a monotonic weighted edge search strategy, where each edge is cleaned only once. This result proves the NP-completeness of the problem.     

Revisiting dynamic programming for finding optimal subtrees in trees

In this paper we revisit an existing dynamic programming algorithm for finding optimal subtrees in edge weighted trees. This algorithm was sketched by Maffioli in a technical report in 1991. First, we adapt this algorithm for the application to trees that can have both node and edge weights. Second, we extend the algorithm such that it does not only deliver the values of optimal trees, but also the trees themselves. Finally, we use our extended algorithm for developing heuristics for the k-cardinality tree problem in undirected graphs G with node and edge weights. This NP-hard problem consists of finding in the given graph a tree with exactly k edges such that the sum of the node and the edge weights is minimal. In order to show the usefulness of our heuristics we conduct an extensive computational analysis that concerns most of the existing problem instances. Our results show that with growing problem size the proposed heuristics reach the performance of state-of-the-art metaheuristics. Therefore, this study can be seen as a cautious note on the scaling of metaheuristics.     

An algorithm and upper bounds for the weighted maximal planar graph problem

In this paper, we investigate the weighted maximal planar graph (WMPG) problem. Given a complete, edge-weighted, simple graph, the WMPG problem involves finding a subgraph with the highest sum of edge weights that is maximal planar, namely, it can be embedded in the plane without any of its edges intersecting, and no additional edge can be added to the subgraph without violating its planarity. We present a new integer linear programming (ILP) model for this problem. We then develop a cutting-plane algorithm to solve the WMPG problem based on the proposed ILP model. This algorithm enables the problem to be solved more efficiently than previously reported algorithms. New upper bounds are also provided, which are useful in evaluating the quality of heuristic solutions or in generating initial solutions for meta-heuristics. Computational results are reported for a set of 417 test instances of size varying from 6 to 100 nodes including 105 instances from the literature and 312 randomly generated instances. The computational results indicate that instances with up to 24 nodes can be solved optimally in reasonable computational time and the new upper bounds for larger instances significantly improve existing upper bounds.     

A primal-dual method for approximating tree cover with two weights

The tree cover (TC) problem is to compute a minimum weight connected edge set, given a connected and edge-weighted graph G, such that its vertex set forms a vertex cover for G. Unlike related problems of vertex cover or edge dominating set, weighted TC is not yet known to be approximable in polynomial time as well as the unweighted version is. Moreover, the best approximation algorithm known so far for weighted TC is far from practical in its efficiency. In this paper we consider a restricted version of weighted TC, as a first step towards better approximation of general TC, where only two edge weights differing by at least a factor of 2 are available. It will be shown that a factor 2 approximation can be attained efficiently (in the complexity of max flow) in this case by a primal-dual method. Even under the limited weights as such, the primal-dual arguments used will be seen to be quite involved, having a nontrivial style of dual assignments as an essential part, unlike the case of uniform weights.     

On weighted multiway cuts in trees

A min—max theorem is developed for the multiway cut problem of edge-weighted trees. We present a polynomial time algorithm to construct an optimal dual solution, if edge weights come in unary representation. Applications to biology also require some more complex edge weights. We describe a dynamic programming type algorithm for this more general problem from biology and show that our min—max theorem does not apply to it.Corresponding author.Research of the author was supported by the A. v. Humboldt-Stiftung and the U.S. Office of Naval Research under the contract N-0014-91-J-1385.     

Approximation of Dense-n/2-Subgraph and the Complement of Min-Bisection

We consider the DENSE-n/2-SUBGRAPH problem, i.e., determine a block of half number nodes from a weighted graph such that the sum of the edge weights, within the subgraph induced by the block, is maximized. We prove that a strengthened semidefinite relaxation with a mixed rounding technique yields a 0.586 approximations of the problem. The previous best-known results for approximating this problem are 0.25 using a simple coin-toss randomization, 0.48 using a semidefinite relaxation, 0.5 using a linear programming relaxation or another semidefinite relaxation. In fact, an un-strengthened SDP relaxation provably yields no more than 0.5 approximation. We also consider the complement of the graph MIN-BISECTION problem, i.e., partitioning the nodes into two blocks of equal cardinality so as to maximize the weights of non-crossing edges. We present a 0.602 approximation of the complement of MIN-BISECTION.     

The interval Branch-and-Prune algorithm for the discretizable molecular distance geometry problem with inexact distances

The Distance Geometry Problem in three dimensions consists in finding an embedding in ${\mathbb{R}^3}$ of a given nonnegatively weighted simple undirected graph such that edge weights are equal to the corresponding Euclidean distances in the embedding. This is a continuous search problem that can be discretized under some assumptions on the minimum degree of the vertices. In this paper we discuss the case where we consider the full-atom representation of the protein backbone and some of the edge weights are subject to uncertainty within a given nonnegative interval. We show that a discretization is still possible and propose the iBP algorithm to solve the problem. The approach is validated by some computational experiments on a set of artificially generated instances.     

A nonconvex quadratic optimization approach to the maximum edge weight clique problem

The maximum edge weight clique (MEWC) problem, defined on a simple edge-weighted graph, is to find a subset of vertices inducing a complete subgraph with the maximum total sum of edge weights. We propose a quadratic optimization formulation for the MEWC problem and study characteristics of this formulation in terms of local and global optimality. We establish the correspondence between local maxima of the proposed formulation and maximal cliques of the underlying graph, implying that the characteristic vector of a MEWC in the graph is a global optimizer of the continuous problem. In addition, we present an exact algorithm to solve the MEWC problem. The algorithm is a combinatorial branch-and-bound procedure that takes advantage of a new upper bound as well as an efficient construction heuristic based on the proposed quadratic formulation. Results of computational experiments on some benchmark instances are also presented.