Narrow Results

We look at well-known polynomial-time approximation algorithms for the optimization problem MAX-CLIQUE (“find the size of the largest clique in a graph”) with regard to how easy it is to compute the actual cliques yielded by these approximation algorithms. We show that even for two “pretty useless” deterministic polynomial-time approximation algorithms, it is unlikely that the resulting clique can be computed efficiently in parallel. We also show that for each non-deterministic algorithm, it is unlikely that there is some deterministic polynomial-time algorithm that decides whether any given vertex appears in some clique yielded by that nondeterministic algorithm.

A Minimum Vertex Cover is the smallest set of vertices whose removal completely disconnects a graph. In this paper, we perform experiments on a number of graphs from standard complex networks databases addressing the problem of finding a "good" vertex cover (finding an optimum is a NP-Hard problem). In particular, we take advantage of the ubiquitous power law distribution present on many complex networks. In our experiments, we show that running a greedy algorithm in a power law graph we can obtain a very small vertex cover typically about 1.02 times the theoretical optimum. This is an interesting practical result since theoretically we know that: (1) In a general graph, on n vertices a greedy approach cannot guarantee a factor better than ln n; (2) The best approximation algorithm known at the moment is very involved and has a much larger factor of . In fact, in the context of approximation within a constant factor, it is conjectured that there is no (2 – ϵ)-approximation algorithm for the problem; (3) Even restricted to power law graphs and probabilistic guarantees, the best known approximation rate is 1.5.

We analyze here a pure greedy hot-potato routing strategy on a two-dimensional mesh of n² nodes. We specifically study the case of n² packets, originating one per node, to be delivered at random uniform destinations. Each packet attempts to follow the shortest path leading first to the destination row/column (whichever is closest) and then to the actual destination node. A deflection policy ia adopted to solve conflicts. We prove that all packets are delivered to the destinations in average time O(nlogn). The average is taken over all possible destination functions. No average case analysis of pure greedy hot-potato routing was known up to now.

In view of the complex background of images and the segmentation difficulty, a sparse representation and supervised discriminative learning were applied to image segmentation. The sparse and over-complete representation can represent images in a compact and efficient manner. Most atom coefficients are zero, only a few coefficients are large, and the nonzero coefficient can reveal the intrinsic structures and essential properties of images. Therefore, sparse representations are beneficial to subsequent image processing applications. We first described the sparse representation theory. This study mainly revolved around three aspects, namely a trained dictionary, greedy algorithms, and the application of the sparse representation model in image segmentation based on supervised discriminative learning. Finally, we performed an image segmentation experiment on standard image datasets and natural image datasets. The main focus of this thesis was supervised discriminative learning, and the experimental results showed that the proposed algorithm was optimal, sparse, and efficient.

This paper presents two greedy scheduling algorithms for recovery of the damaged lifeline network. Unlike genetic algorithm or simulated annealing, the proposed algorithms do not involve random processes. One of the algorithms is for assigning multiple heterogeneous engineers and preparing schedules for repairing independent damaged components, while the other is for finding repair schedule for a single engineer considering network constraint. Both the algorithms use rate of benefit gain as an index in deciding which component should be repaired next, and by whom. The target use of these algorithms is to serve as an initial solution for a multi-agent system which includes fine grain details. With numerical experiments, it is demonstrated that the proposed algorithms can find near-optimal repair schedules and solve problems involving large number of variables.

Kernels have become an integral part of most data classification algorithms. However, the kernel parameters are generally not optimized during learning. In this work a novel adaptive technique called Sequential Function Approximation (SFA) has been developed for classification that determines the values of the control and kernel hyper-parameters during learning. This tool constructs sparse radial basis function networks in a greedy fashion. Experiments were carried out on synthetic and real-world data sets where SFA had comparable performance to other popular classification schemes with parameters optimized by an exhaustive grid search.

An upper bound for sorting permutations with an operation estimates the diameter of the corresponding Cayley graph and an exact upper bound equals the diameter. Computing tight upper bounds for various operations is of theoretical and practical (e.g., interconnection networks, genetics) interest. Akers and Krishnamurthy gave a Ω(n! n²) time method that examines n! permutations to compute an upper bound, f(Γ), to sort any permutation with a given transposition tree T, where Γ is the Cayley graph corresponding to T. We compute two intuitive upper bounds γ and δ′ each in O(n²) time for the same, by working solely with the transposition tree. Recently, Ganesan computed β, an estimate of the exact upper bound for the same, in O(n²) time. Our upper bounds are tighter than f(Γ) and β, on average and in most of the cases. For a class of trees, we prove that the new upper bounds are tighter than β and f(Γ).

Most research on algorithms for combinatorial optimization use the costs of the elements in the ground set for making decisions about the solutions that the algorithms would output. For traveling salesman problems, this implies that algorithms generally use arc lengths to decide on whether an arc is included in a partial solution or not. In this paper we study the effect of using element tolerances for making these decisions. We choose the traveling salesman problem as a model combinatorial optimization problem and propose several greedy algorithms for it based on tolerances. We report extensive computational experiments on benchmark instances that clearly demonstrate that our tolerance-based algorithms outperform their weight-based counterpart. This indicates that the potential for using tolerance-based algorithms for various optimization problems is high and motivates further investigation of the approach.