Catálogo de publicaciones - libros

The capacitated tree-routing problem (CTR) in a graph  = (,) consists of an edge weight function :→, a sink  ∈ , a terminal set  ⊆  with a demand function :→, a routing capacity > 0, and an integer edge capacity  ≥ 1. The CTR asks to find a partition of and a set of trees of such that each spans  ∪ {} and satisfies . A subset of trees in can pass through a single copy of an edge  ∈  as long as the number of these trees does not exceed the edge capacity ; any integer number of copies of are allowed to be installed, where the cost of installing a copy of is (). The objective is to find a solution that minimizes the installing cost . In this paper, we propose a -approximation algorithm to the CTR, where is any approximation ratio achievable for the Steiner tree problem.

In this paper we give ratio 4 deterministic and randomized approximation algorithms for problem in bipartite tournaments. We also generalize these results to give a factor 4 deterministic approximation algorithm for problem in multipartite tournaments.

Considering the fact that there exist information asymmetry (hidden information) in routing phase, and moral hazard (hidden action) in forwarding phase in autonomous Ad hoc network, this paper argues that economic-based mechanisms play both a signaling and a sanctioning role, which reveal the node’s true forwarding cost in routing phase while provide incentives to nodes to exert reasonable effort in forwarding phase, that is, the role of economic-inspired mechanisms in information asymmetry is to induce learning whereas the role of such mechanisms in moral hazard settings is to constrain behavior. Specifically, this paper conducts the following works: considering the mutually dependent link cost, we demonstrate that, for each participant, truth-telling is the risk dominant strategy in VCG-like routing mechanism based on analysis of extensive game form. Then, Individual rationality (IR) and Incentive Compatibility (IC) constraints are formally offered, which should be satisfied by any game theoretical routing and forwarding scheme. And different solution concepts are investigated to characterize the economic meanings of two kind forwarding approaches, that is, Nash equilibrium with no per-hop monitoring and dominant strategy equilibrium with per-hop monitoring.

Many verification approaches based on automata theory are related to the language containment problem, which is PSPACE-complete for nondeterministic automata. To avoid such a complexity, one may use simulation as an approximation to language containment, since simulation implies language containment and computing simulation is a polynomial time problem. As it is an approximation, there exists a gap between simulation and language containment, therefore there has been an effort to develop methods to narrow the gap while keeping the computation in polynomial time. In this paper, we present such an approach by building a Büchi  automaton based on partial marked subset construction to be used in the computation of simulation relation, such that the automaton preserves the original language and has a structure that helps identify more pairs of automata that are in language containment relation. This approach is an improvement to the fair--simulation method [3].

For temporal and epistemic property CTLK we propose a new symbolic model checking technique based on Quantified Boolean Formula(QBF). The verification approach is based on an adaption of the technique of bounded model checking. We decide the validity of a CTLK formula in the finite reachable state space of a system, and reduce the validity to a QBF which is satisfiable if and only if is validated. The new technique avoids the space blow up of BDDs, and sometimes speeds up the verification.

Formal language learning models have been widely investigated in the last four decades. But it was not until recently that the model of learning from corrections was introduced. The aim of this paper is to make a further step towards the understanding of the classes of languages learnable with correction queries. We characterize these classes in terms of triples of definite finite tell-tales. This result allowed us to show that learning with correction queries is strictly more powerful than learning with membership queries, but weaker than the model of learning in the limit from positive data.

Based on limiting recursive function proposed by Gold [2], learnable algorithm on the continuum are defined. We discuss the class of learnable real numbers and learnable real sequence in various ways. In this paper we summarize some attempts to classify the learnably approximable real numbers by the convergence rates of the corresponding computable(or learnable) sequences of rational numbers.

Existing work on scheduling with energy concern has focused on minimizing the energy for completing all jobs or achieving maximum throughput [19,2,7,13,14]. That is, energy usage is a secondary concern when compared to throughput and the schedules targeted may be very poor in energy efficiency. In this paper, we attempt to put energy efficiency as the primary concern and study how to maximize throughput subject to a user-defined threshold of energy efficiency. We first show that all deterministic online algorithms have a competitive ratio at least , where is the max-min ratio of job size. Nevertheless, allowing the online algorithm to have a slightly poorer energy efficiency leads to constant (i.e., independent of ) competitive online algorithm. On the other hand, using randomization, we can reduce the competitive ratio to (log) without relaxing the efficiency threshold. Finally we consider a special case where no jobs are “demanding” and give a deterministic online algorithm with constant competitive ratio for this case.

The airlines in the real world form small-world network. This implies that they are constructed with an ad hoc strategy. The small-world network is not so bad from the viewpoints of customers and managers. The customers can fly to any destination through a few airline hubs, and the number of airlines is not so many comparing to the number of airports. However, clearly, it is not the best solution in either viewpoint since there is a trade off. In this paper, one of the extreme cases, which is the standpoint of the manager, is considered; we assume that customers are silent and they never complain even if they are required to transit many times. This assumption is appropriate for some transportation service and packet communication. Under this assumption, the airline problem is to construct the least cost connected network for given distribution of the populations of cities with no a priori connection. First, we show an efficient algorithm that produces a good network which is minimized the number of vacant seats. The resultant network contains at most connections (or edges), where is the number of cities. Next we aim to minimize not only the number of vacant seats, but also the number of airline connections. The connected network with the least number of edges is a tree which has exactly  − 1 connections. However, the problem to construct a tree airline network with the minimum number of vacant seats is -complete. We also propose efficient approximation algorithms to construct a tree airline network with the minimum number of vacant seats.

We describe a computing method of the computable (or constructive) real numbers based on analysis of expressions. This method take precision estimate into account in order to get a better algorithm than Ménissier-Morain’s method, which is also based on the representation of constructive reals. We solve two problems which appear in exact real arithmetic based on the representation of constructive reals. First, by balancing every item’s precision in the expression, we can avoid unnecessary precision growth. Second, by distributing different weights to different operations, we can make sure that complex operations do not waste much time when to compute the whole expression. In these ways, we finally get a more efficient and proper method than prior implementations.