Search

The new characterization for maximum matching in bipartite graphs given by Balinski and Gonzalez is based on "strong spanning trees" and is independent on the classical notion of augmenting path. However, the algorithm that they derived runs in $0(\mid V \mid \mid E \mid)$ time for bipartite graphs with $\mid V \mid$ nodes and $\mid E \mid$ edges, and so it is not competitive with the $0(\sqrt{\mid V \mid} \mid E \mid)$ algorithm of Hopcroft and Karp. In this paper we prove that the basic results given by Hopcroft and Karp can also be obtained using the new characterization, allowing us to develop a competitive algorithm.

This paper introduces an improved evolutionary algorithm based ontheImperialist Competitive Algorithm (ICA), called Quad Countries Algorithm (QCA). The Imperialist Competitive Algorithm is inspired by socio-political process of imperialistic competition in the real world and has shown its reliable performance in optimization problems. In the ICA, the countries are classified into two groups: Imperialists and Colonies. However, in the QCA, two other kinds of countries including Independent and Seeking Independence are added to the countries collection. In the ICA also the Imperialists' positions are fixed, while in the QCA Imperialists may move. The proposed algorithm was tested by well-known benchmarks, and the compared results of the QCA with results of ICA, GA [12], PSO [12], PS-EA [12] and ABC [11] show that the QCA has better performance than all mentioned algorithms. Among them, the QCA, ABC and PSO have better performance respectively in 50%, 41.66% and 8.33% of all cases.

In many fault detection problems, the goal is to identify defective items from a set of items with a minimum number of tests. Each test is on a subset of items, which tells whether the subset contains a defective item or not. The concept of competitive algorithm has been developed to relate the properties of the group testing algorithms that assume that the number of defective items $d$ is known, to those without any a priori knowledge on $d$. A new concept of strongly competitive algorithm is defined that relates different characteristics of these two classes of algorithms and present an interesting relationship between the two concepts competitive and strongly competitive. A strongly competitive algorithm is also presented.

We consider the problem of a searcher exploring an initially unknown weighted planar graph G. When the searcher visits a vertex v, it learns of each edge incident to v. The searcher's goal is to visit each vertex of G, incurring as little cost as possible. We present a constant competitive algorithm for this problem.

Algorithms for the group testing problem when there is no a priori information on the number of defective items are considered. The efficiency criterion used is the competitive ratio, which is the ratio of the number of tests required by an algorithm when there is no a priori information on the number of defective items, to the number of tests required by an optimal algorithm when the number of defective items is known in advance. A new algorithm is presented, and it is shown that the competitive ratio of this algorithm is 2. This result is an improvement over a previous algorithm due to Du and Hwang (1990) the competitive ratio of which is 2.75. It also proves a conjecture made by Du and Hwang. A new application of group testing techniques for high-speed network is discussed.

We propose a new algorithm, called Equipoise, for the k-server problem, and we prove that it is two-competitive for two servers and 11-competitive for three servers. For k = 3, this is a substantial improvement over previously known constants. The algorithm uses several general techniques - convex hulls, work functions, and forgiveness.

Many fault-detection problems fall into the following model: There is a set of $n$ items, some of which are defective. The goal is to identify the defective items by using the minimum number of tests. Each test is on a subset of items and tells whether the subset contains a defective item or not. Let $M_{\alpha}(d, n) (M_{\alpha}(d\,|\,n))$ denote the maximum number of tests for an algorithm $\alpha$ to identify $d$ defectives from a set of $n$ items provided that $d$, the number of defective items, is known (unknown) before the testing. Let $M(d, n) = \min_{\alpha} M_{\alpha}(d, n)$. An algorithm $\alpha$ is called a {\it competitive algorithm\/} if there exist constants $c$ and $a$ such that for all $n > d > 0$, $M_{\alpha}(d\,|\,n) \leq cM(d, n) + a$. This paper confirms a recent conjecture that there exists a bisecting algorithm $A$ such that $M_A(d\,|\,n) \leq 2M(d, n) + 1$. Also, an algorithm $B$ such that $M_B(d\,|\,n) \leq 1.65M(d, n) + 10$ is presented.

We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more competitive than the best previous randomized algorithm due to Irani. Our algorithm uses randomness only during an initialization phase, and from then on runs completely deterministically. It is the first randomized competitive algorithm with this property to beat the deterministic lower bound. We generalize our approach to a model in which access costs are fixed but update costs are scaled by an arbitrary constantd. We prove lower bounds for deterministic list update algorithms and for randomized algorithms against oblivious and adaptive on-line adversaries. In particular, we show that for this problem adaptive on-line and adaptive off-line adversaries are equally powerful.

Considering the problem that the target recognition based on DS evidence theory cannot satisfy the real-time requirement of an intelligent bioacoustic frightening system, this chapter proposes an improved DS competitive algorithm based on the matrix analysis and the weighted evidence. It uses reasoning in turn to integrate evidences, computes competitive results in the combinations of n group trust function to solve the problem of evidence conflict, and the weighted evidences substitute for the conflict evidences. The algorithm uses analysis matrix to overcome the problem of huge calculations and reduces the burden on the node. Thus, simulation was made for a practical example, and the numerical experiment results are adopted to prove its effectiveness.

Course timetabling consists in scheduling a sequence of lectures while satisfying various constraints. In this paper, we develop and study the performance of a memetic algorithm, designed to solve a variant of the course timetabling problem. Our aim here is twofold: to develop a competitive algorithm, and to investigate, more generally, the applicability of evolutionary algorithms to timetabling. To this end, an algorithm is first introduced and tested using a benchmark set. Comparison with other algorithms shows that our algorithm achieves better results in some, but not all instances, signifying strong and weak points. Subsequently, more comprehensive analyses are performed in relation with another evolutionary algorithm that uses strictly group-based operators. Ultimately, empirical results and analyses lead us to question the exclusive use of group-based evolutionary operators for timetabling problems.

Graph Theory, In the frequency allocation problem, we are given a cellular telephone network whose geographical coverage area is divided into cells, where phone calls are serviced by assigned frequencies, so that none of the pairs of calls emanating from the same or neighboring cells is assigned the same frequency. The problem is to use the frequencies efficiently, i.e. minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph, where each vertex knows its position in the graph. We present a 1-local 33/24-competitive distributed algorithm for multicoloring a hexagonal graph, thereby improving the previous 1-local 7/5-competitive algorithm.

International audience; A mobile robot, represented by a point moving along a polygonal line in the plane, has to explore an unknown polygon and return to the starting point. The robot has a sensing area which can be a circle or a square centered at the robot. This area shifts while the robot moves inside the polygon, and at each point of its trajectory the robot "sees" (explores) all points for which the segment between the robot and the point is contained in the polygon and in the sensing area. We focus on two tasks: exploring the entire polygon and exploring only its boundary. We consider several scenarios: both shapes of the sensing area and the Manhattan and the Euclidean metrics. We focus on two quality benchmarks for exploration performance: optimality (the length of the trajectory of the robot is equal to that of the optimal robot knowing the polygon) and competitiveness (the length of the trajectory of the robot is at most a constant multiple of that of the optimal robot knowing the polygon). Most of our results concern rectilinear polygons. We show that optimal exploration is possible in only one scenario, that of exploring the boundary by a robot with square sensing area, starting at the boundary and using the Manhattan metric. For this case we give an optimal exploration algorithm, and in all other scenarios we prove impossibility of optimal exploration. For competitiveness the situation is more optimistic: we show a competitive exploration algorithm for rectilinear polygons whenever the sensing area is a square, for both tasks, regardless of the metric and of the starting point. Finally, we show a competitive exploration algorithm for arbitrary convex polygons, for both shapes of the sensing area, regardless of the metric and of the starting point.

We consider dynamic speed scaling on a single processor and study the tradeoff between throughput and energy for deadline scheduling. Specifically, we assume each job is associated with a user-defined value (or importance) and a deadline. We allow scheduling algorithms to discard some of the jobs (i.e., not finishing them) and the objective is to minimize the total energy usage plus the total value of jobs discarded. We give new online algorithms under both the unbounded-speed and bounded-speed models. When the maximum speed is unbounded, we give an O(1)-competitive algorithm. This algorithm relies on a key notion called the profitable speed, which is the maximum speed beyond which processing a job costs more energy than the value of the job. When the processor has a bounded maximum speed T, we show that no O(1)- competitive algorithm exists and more precisely, the competitive ratio grows with the penalty ratio of the input, which is defined as the ratio between the maximum profitable speed of a job to the maximum speed T. On the positive side, we give an algorithm with a competitive ratio whose dependency on the penalty ratio almost matches the lower bound.

The incremental median problem consists of finding an incremental sequence of facility sets F1 ⊆ F2 ⊆ ... ⊆ Fn, where each Fk contains at most k facilities. We say that this incremental medians sequence is c-competitive if the cost of each Fk is at most c times of the optimum cost of k-median problem. The smallest such c is called the competitive ratio. A particular case of the problem is considered in this paper: both the clients and facilities are located on the real line. [5] and [14] presented a polynomial-time algorithm for this one-dimensional case that computes an incremental sequence with competitive ratio 8. The best algorithm available has competitive ratio (1 + √2)2 ≈ 5.83[19]. In this paper we give an improved polynomial-time algorithm with competitive factor 4.

In the generalized Steiner tree problem, we find a minimumcost set of edges to connect a given set of source-sink pairs. In the online version of this problem, the source-sink pairs arrive over time. Agrawal, Klein, and Ravi give a 2-approximation algorithm for the offline problem; Berman and Coulston give an O(log n)-competitive algorithm for the online problem. Goemans and Williamson subsequently generalized the offline algorithm of Agrawal et al. to handle a large class of problems they called constrained forest problems, and other problems, such as the prize-collecting Steiner tree problem. In this paper, we show how to combine the ideas of Goemans and Williamson and those of Berman and Coulston to give an O(log n)-competitive algorithm for online constrained forest problems, including an online version of the prize-collecting Steiner tree problem.

Let MA(n,d) denote the maximum number of group tests for a group testing algorithm A to identify d defectives from a set of n items when d is known, and let MA(n∣d) denote the number when d is unknown. Define M(n,d) = minA MA(n,d). An algorithm A is called a competitive algorithm if there exist constants c and a such that for all n > d ≥ 0, MA(n∣d) ≤ cM(n,d) + a. In this paper, we present some competitive group testing algorithms.

In this paper, we investigate investment strategies that can rebalance their target portfolio vectors at arbitrary investment periods. These strategies are called semiconstant rebalanced portfolios in Blum and Kalai and Helmbold et al. Unlike a constant rebalanced portfolio, which must rebalance at every investment interval, a semiconstant rebalanced portfolio rebalances its portfolio only on selected instants. Hence, a semiconstant rebalanced portfolio may avoid rebalancing if the transaction costs outweigh the benefits of rebalancing. In a competitive algorithm framework, we compete against all such semiconstant portfolios with an arbitrary number of rebalancings and corresponding rebalancing instants. We investigate this framework with and without transaction costs and demonstrate sequential portfolios that asymptotically achieve the wealth of the best semiconstant rebalanced portfolios whose number of rebalancings and instants of rebalancings are tuned to the individual sequence of price relatives.

In the on-line financial leasing problem, an on-line player, who is the leaser, is given the job of deciding whether to buy the equipment initially or to rent it according to the financial leasing contract, without knowing the future interest rates over the whole rental time. This paper studies the on-line financial leasing problem from the perspective of competitive analysis theory. To begin with, based on the formulation of relevant parameters, a Financial Leasing Competitive Algorithm is established. Following that, corollary and numerical examples concerning competitive analysis for this algorithm are given. Finally, some future research directions are pointed out.

In the frequency allocation problem we are given a cellular tephone network whose geographical coverage area is divided into cells where phone calls are serviced by frequencies assigned to them, so that none of the pairs of calls emanating from the same or neighboring cells is assigned the same frequency. The problem is to use the frequencies efficiently, i.e. minimize the span of used frequencies. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph. In this paper we present a 1-local 17/12-competitive distributed algorithm for a multicoloring of hexagonal graph, thereby improving the competitiveness ratio of previously known best 1-local 13/9-competitive algorithm (see [1]).

In multiprocessor scheduling with rejection the jobs are characterized by a processing time and a penalty and it is possible to reject the jobs. The goal is to minimize the makespan of the schedule for the accepted jobs plus the sum of the penalties of the rejected jobs. In this paper we present a new online algorithm for the problem. Our algorithm is a parameter learning extension of the total reject penalty algorithm. The efficiency of the algorithm is investigated by an experimental analysis. In this paper we develop a new algorithm for the solution of the online scheduling with rejection problem on identical machines. The algorithm is based on the idea of learning the parameter of the Reject Total Penalty (RTP) algorithm. We measure the efficiency of the new algorithm by an experimental analysis. The problem of scheduling with rejection is defined in (2). In this model, it is possible to reject the jobs. The jobs are characterized by a processing time and a penalty. The goal is to minimize the makespan of the schedule for the accepted jobs plus the sum of the penalties of the rejected jobs. In the online case a 2.618- competitive algorithm is given for arbitrary number of machines. This algorithm is called Reject Total Penalty (RTP). One basic idea in scheduling with rejection is to compare the penalty and the load (processing time divided by the number of machines) of the job, and reject the job in the case when the penalty is smaller. This greedy algorithm can make a bad decision when the number of machines is large and this makes possible to appear large jobs with small loads. RTP handles these jobs more carefully. We give the detailed definition in the next section. In (2) a further, 1.618-competitive algorithm is presented in the case of 2 machines. Matching lower bounds are also given. In the offline case an FPTAS is presented for fixed number

We provide a general scheme for constructing monotone algorithms for a wide class $\mathcal{C}$ of scheduling problems Q|prec,r j |γ on related machines with precedence constraints and/or release dates. Our scheme works in the offline and the online setting. It takes as input two approximation/competitive algorithms for the (simpler) scheduling problems P|prec,r j |γ on identical machines and 1|prec,r j |γ on a single machine and then generically constructs a monotone approximation/ competitive algorithm for the problem on related machines. Monotone algorithms are necessary and sufficient for the design of truthful scheduling mechanisms in the setting with selfish machines. The algorithms constructed by our scheme are among the first monotone algorithms for scheduling problems with precedence constraints. For example, we show that our scheme applies to the problems of minimizing the makespan or the weighted sum of completion times when the jobs have precedence constraints and/or release dates.

According to the principle of unity of opposition in the natural tree growing and wilting, the competitive algorithm of simulating natural tree growth is presented in this paper. The algorithm is also used to optimize a tree-shaped line antenna whose directive gain is higher than that of the traditional antennas in the same size.

In this paper a Kohonen self-organizing competitive algorithm is considered. A formal approach to classification problem, basing on equivalence relations, is proposed. The Kohonen neural networks are considered as classifying systems. The main topic of this paper is proposal of applying stereographic projection as an input signals normalization procedure. Both theoretical justification is discussed and results of experiments are presented. It turns out that the introduced normalization procedure is effective.

We consider online scheduling algorithms in the dynamic speed scaling model, where a processor can scale its speed between 0 and some maximum speed T. The processor uses energy at rate s a when run at speed s, where a>¿1 is a constant. Most modern processors use dynamic speed scaling to manage their energy usage. This leads to the problem of designing execution strategies that are both energy efficient, and yet have almost optimum performance. We consider two problems in this model and give essentially optimum possible algorithms for them. In the first problem, jobs with arbitrary sizes and deadlines arrive online and the goal is to maximize the throughput, i.e. the total size of jobs completed successfully. We give an algorithm that is 4-competitive for throughput and O(1)-competitive for the energy used. This improves upon the 14 throughput competitive algorithm of Chan et al. [10]. Our throughput guarantee is optimal as any online algorithm must be at least 4-competitive even if the energy concern is ignored [7]. In the second problem, we consider optimizing the trade-off between the total flow time incurred and the energy consumed by the jobs. We give a 4-competitive algorithm to minimize total flow time plus energy for unweighted unit size jobs, and a (2¿+¿o(1)) a/ln a-competitive algorithm to minimize fractional weighted flow time plus energy. Prior to our work, these guarantees were known only when the processor speed was unbounded (T¿=¿8¿) [4].

A technique for finding in a graph an independent set with maximum cardinality is presented. It consists of an implicit enumeration procedure; the procedure uses at various stages bounds on the independence number of a subgraph. These are obtained by applying an adaptation of Tabu Search. Computational results are given which show that with Tabu Search a competitive algorithm is obtained; the case of randomly generated graphs having up to 450 or 500 nodes (with edge density 0.5) can be handled by this approach.

We present an algorithm for multichannel blind deconvolution of seismic signals, which exploits lateral continuity of earth layers by dynamic programming approach. We assume that reflectors in consecutive channels, related to distinct layers, form continuous paths across channels. We introduce a quality measure for evaluating the quality of a continuous path, and iteratively apply dynamic programming to find the best continuous paths. The improved performance of the proposed algorithm and its robustness to noise, compared to a competitive algorithm, are demonstrated using simulated and real seismic data examples.

In the problem of Online Call Admission in Optical Networks, briefly called oca, we are given a graph G=(V,E) together with a set of wavelengths W (χ:=|W|) and a finite sequence σ=r1,r2,... of calls which arrive in an online fashion. Each call rj specifies a pair of nodes to be connected. A lightpath is a path in G together with a wavelength λ ∈ W. Upon arrival of a call, an online algorithm must decide immediately and irrevocably whether to accept or to reject the call without any knowledge of calls which appear later in the sequence. If the call is accepted, the algorithm must provide a lightpath to connect the specified nodes. The essential restriction is the wavelength conflict constraint: each wavelength is available only once per edge, which implies that two lightpaths sharing an edge must have different wavelengths. The objective in oca is to maximize the overall profit, that is, the number of accepted calls. A result by Awerbuch et al. states that a c-competitive algorithm for oca with one wavelength, i.e., χ:=|W|=1, implies a (c+1)-competitive algorithm for general numbers of wavelengths. However, for instance, for the line with n+1 nodes, a lower bound of n for the competitive ratio of deterministic algorithms for χ=1 makes this result void in many cases. We provide a deterministic competitive algorithm for χ>1 wavelengths which achieves a competitive ratio of $\chi(\sqrt[\chi]{n} + 2)$ on the line with n+1 nodes. As long as χ>1 is fixed, this is the first competitive ratio which is sublinear in n+1, the number of nodes.

We consider 2-server algorithms with time complexity O(1) per each request. We show that the previously known algorithm BALANCE2 has competitiveness constant not better than 6, and present another algorithm whose competitiveness constant is 4.

We continue the development of our Voronoi Galaxy Cluster Finder (VGCF) technique by applying it to galaxy catalogs obtained with B and R band observations of four high galactic latitude fields of 0.5x0.5 square degrees each. These fields are deep R_lim ~23, B_lim ~26 and partially overlap the Palomar Distant Cluster Survey (PDCS) fields at 0h and 2h. We run the VGCF also on the original V and I bands PDCS galaxy catalogs. We identify a total of 48 clusters that are particularly reliable being detected in at least two bands. The analysis of color-magnitude diagrams and, in a few cases, spectroscopic observations allow us to further increase the reliability of 25 of the 48 clusters. For these 26 clusters we also estimate redshifts that fall in the approximate range 0.2 < z < 0.6. We detect 41 VGCF clusters within the strict limits of the PDCS fields at 0h and 2h. The PDCS catalog for the same regions consists of 28 clusters. The two catalogs have 20 clusters in common. These clusters together with the remaining PDCS and VGCF clusters lead to a total number of 46 "independent" clusters. The total number of clusters is therefore 20% larger than the number of VGCF clusters and more than 60% larger than the number of PDCS clusters. These results confirm a) that the VGCF is a competitive algorithm for the identification of optical clusters, and b) that a combined catalog of matched-filter and VGCF clusters constitutes a significant progress toward a more complete selection of clusters from bidimensional optical data., 15 pages, 6 figures, accepted in A&A

Images are often contaminated by impulse noise. The major drawback of median filtering and its variants - that are widely used for removing impulsive noise - is the blurring effect for large window sizes and low noise suppression for small window sizes. In this paper, a fuzzy-competitive algorithm for removing impulse noise in images is proposed. The proposed algorithm utilized fuzzy inference systems for impulse detection. The detected impulses are then removed using long-range correlation information in a competitive scheme. The experimental results show that the performance of our method in removing impulsive noises is better than that of most other state-of-the-art methods

The authors consider the problem faced by a newborn that must explore and learn an unknown room with obstacles in it. They seek algorithms that achieve a bounded ratio of the worst-case distance traversed in order to see all visible points of the environment (thus creating a map), divided by the optimum distance needed to verify the map. The situation is complicated by the fact that the latter offline problem (optimally verifying a map) is NP-hard and thus must be solved approximately. Although the authors show that there is no such competitive algorithm for general obstacle courses, they give a competitive algorithm for the case of a polygonal room with a bounded number of obstacles in it. >

We study the scheduling problem of minimizing the maximum starting time on-line. The goal is to minimize the last time that a job starts. We show that while the greedy algorithm has a competitive ratio of ?(log m), we can give a constant competitive algorithm for this problem. We also show that the greedy algorithm is optimal for resource augmentation in the sense that it requires 2m - 1 machines to have a competitive ratio of 1, whereas no algorithm can achieve this with 2m - 2 machines.

Nešetřil and Sopena introduced a concept of oriented game chromatic number and developed a general technique for bounding this parameter. In this paper, we combine their technique with concepts introduced by several authors in a series of papers on game chromatic number to show that for every positive integer $k$, there exists an integer $t$ so that if ${\cal C}$ is a topologically closed class of graphs and ${\cal C}$ does not contain a complete graph on $k$ vertices, then whenever $G$ is an orientation of a graph from ${\cal C}$, the oriented game chromatic number of $G$ is at most $t$. In particular, oriented planar graphs have bounded oriented game chromatic number. This answers a question raised by Nešetřil and Sopena. We also answer a second question raised by Nešetřil and Sopena by constructing a family of oriented graphs for which oriented game chromatic number is bounded but extended Go number is not.

We consider the following motion planning problem for a point robot inside a simple polygon P: starting from an arbitrary point s of P, the robot aims at reaching the closest point t of P from where the entire polygon P can be seen; the robot does not have complete knowledge of P but is equipped with a 360-degree vision system that helps it "see" its surrounding space. We are interested in a competitive path planning algorithm, i.e., one that produces a path whose length does not exceed a constant c times the length of the shortest off-line path tin this case, c x distance(s, t)); the constant c is called the competitive factor. In this paper, we present a new strategy that achieves a competitive factor of similar to3.126, improving over a 4.14-competitive strategy of Icking and Klein and a 3.829-competitive strategy of Lee et al. Our strategy possesses two additional advantages: first, the first point reached from where the entire polygon P is seen is precisely the closest such point to the starting position s, and second, all the points of the path are directly determined in terms of s and of polygon vertices, which implies that an actual robot following the strategy is not expected to deviate much from its course due to numerical error. The competitiveness analysis is based on properties of the class of curves with increasing chords. Algorithm Theory - Swat 2000

We consider the k-server problem , with the additional assumption that (1) the adversary makes only lazy moves (if it has a free server, not matched with our server, then it puts a request on such a server without moving it), and (2) whenever all our servers are matched with his servers, then he announces it to our algorithm. We show a k -competitive algorithm against such an adversary. As with the original server problem, no better than a k -competitive on-line algorithm is possible in this model.

We present the first randomized upper and lower bounds for online multi-threaded paging as introduced by Feuerstein and Strejilevich de Loma [1996]. Our main result is a O(ω log k)-competitive algorithm for unfair infinite multithreaded paging, which is optimal to within a constant factor. We also present algorithms and lower bounds for three other sub-models of multi-threaded paging.

In this paper we present a simple on-line strategy based on a continuous angle bisector approach for searching an unknown street polygon. The proposed strategy achieves a competitive ratio of 1+loge(1+ cos α/2)+δ, where 0≤α≤π, and δ is a given constant greater than zero. By choosing an arbitrarily small value for δ, the value of this ratio is 1.7, which is significantly better than the previous upperbound of 2.83 (derived by Kleinberg [6]), considering that the lowerbound for this problem is √2(> 1.41) (derived by Klein [5]).

In this paper we introduce a generalization of Paging to the case where there are many threads of requests. This models situations in which the requests come from more than one independent source.

Copyright (c) 1997 Elsevier Science B.V. All rights reserved. We study the following counterfeit coin problem: Suppose that there is a set of n coins. Each one is either heavy or light. The goal is to sort them according to weight with a minimum number of weighings on a balance scale. Hu and Hwang gave an algorithm with a competitive ratio of 3 log 3 (all logarithms are base-2). Hu, Chen and Hwang also gave an algorithm with a competitive ratio of 2 log 3. In this paper we give an improved algorithm whose competitive ratio is (3)/(2) log 3.

We consider the problem of a searcher exploring an initially unknown weighted planar graph G. When the searcher visits a vertex v, it learns of each edge incident to v. The searcher's goal is to visit each vertex of G, incurring as little cost as possible. We present a constant competitive algorithm for this problem.

It is well-known that the architecture of a neural network (NN) plays a crucial role on its generalisation capabilities. While conventional NN training algorithms assume a pre-defined NN architecture before training starts, constructive neural network (CoNN) algorithms define the architecture of the NN along with its training. This paper describes the proposal of a new two-class CoNN algorithm named OffTiling, suitable for continuous valued domains and slightly inspired by two other CoNN algorithms found in the literature, the Offset, designed for learning in Boolean domains and the two-class CoNN Tiling algorithm. A comparative analysis of the OffTiling versus four other CoNN algorithms, namely the Pyramid, Tiling, PTI and the TilingLike in ten knowledge domains is presented, showing that the OffTiling can be a competitive algorithm as far as the performance of the network is concerned.

An on-line problem is one in which an algorithm must handle a sequence of requests, satisfying each request without knowledge of the future requests. Examples of on-line problems include scheduling the motion of elevators, finding routes in networks, allocating cache memory, and maintaining dynamic data structures. A competitive algorithm for an on-line problem has the property that its performance on any sequence of requests is within a constant factor of the performance of any other algorithm on the same sequence. This paper presents several general results concerning competitive algorithms, as well as results on specific on-line problems.