Wyniki wyszukiwania - BazTech

1

On the Hardness of Reoptimization with Multiple Given Solutions

Böckenhauer H. J., Hromkovič J., Sprock A.

Fundamenta Informaticae

|

2011

|

Vol. 110, nr 1-4

59-76

EN

In reoptimization, we consider the following scenario: Given an instance of a hard optimization problem together with an optimal solution for it, we want to solve a locally modified instance of the problem. It has recently been shown for several hard optimization problems that their corresponding reoptimization variants remain NP-hard or even hard to approximate whereas they often admit improved approximation ratios. In this paper, we investigate a generalization of the reoptimization concept where we are given not only one optimal solution but multiple optimal solutions for an instance. We prove, for some variants of the Steiner tree problem and the traveling salesman problem, that the known reoptimization hardness results carry over to this generalized setting. Moreover, we consider the performance of local search strategies on reoptimization problems. We show that local search does notwork for solving TSP reoptimization, even in the presence ofmultiple solutions.

2

Fast Object Detection Using Steiner Tree

Xiaoyin D.

Machine Graphics and Vision

|

2010

|

Vol. 19, No. 2

127-142

EN

We propose an approach to speed-up object detection, with an emphasis on settings where multiple object classes are detected. Our method uses a segmentation algorithm to select a small number of image regions on which to run a classifier. Compared to the classical sliding window approach, a significantly smaller number of rectangles is examined, which yields significantly faster object detection. Further, in the multiple object class setting, we show that the computational cost of segmentations can be amortized across objects classes, resulting in an additional speedup. At the heart of our approach is reduction to a directed Steiner tree optimization problem, which we solve approximately in order to select the segmentation algorithm parameters. The solution gives a small set of segmentation strategies that can be shared across object classes. Compared to the sliding window approach, our method results in two orders of magnitude fewer regions considered, and significant (10-15x) computational time speedups on challenging object detection datasets (LabelMe and StreetScenes) while maintaining comparable detection accuracy.

3

Equivalence, Indicators, Quasi-indicators and Optimal Steiner Topologies on Four Points in Space

Weng J.F., Smith J.MacGregor, Brazil M., Thomas D.A.

Fundamenta Informaticae

|

2008

|

Vol. 84, nr 1

135-149

EN

The Steiner tree problem is an intractable optimization problem, which asks for a network, in fact a tree, interconnecting a given point set V in a metric space and minimizing the total length of the network. The tree topology t of the network is called a Steiner topology and a tree T with minimum length with respect to its Steiner topology is called a Steiner tree. As a combinatorial optimization problem, the Steiner tree problem asks for a Steiner tree T with minimum length over all possible topologies t on V. It has been proved that if T is in E3 then the length of T cannot be expressed by radicals even when T spans just 4 points. For such optimization problems in which the objective functions do not have closed form solutions the traditional approach is approximation. In this paper we propose a new approach by introducing some new concepts: equivalence, indicators and quasi-indicators, and then we apply these concepts to the Steiner tree problem. Roughly speaking, a quasi-indicator is a function that is simple to compute but indicates with high probability the optimal solution to the original optimisation problem. For a specific optimisation problem - finding the optimal Steiner topologies on 4 points in space, we demonstrate how to find good quasi-indicators. The extensive computational experiments over 5000 random 4-point sets show that the best quasi-indicator for finding optimal Steiner topologies on 4 points in space is not only easy to compute but also extremely successful with less than 1.5% failures in indicating optimal topologies even if degeneracy of Steiner minimal trees exists. Moreover, within the 1.5% cases of failure, the maximum and the average relative error are 1.5% and 0.2% respectively. Therefore, the performance of the proposed Q-indicator is very good and could be applied to the four vertices surrounding any pair of adjacent Steiner points in a Steiner tree on n ( > 4) points in space to make local improvements to the topology of the Steiner minimal tree in space.