排序方式: 共有49条查询结果,搜索用时 15 毫秒
1.
We consider a service provider (SP) who provides access to a communication network or some other form of on-line services. Users initiate calls that belong to a set of diverse service classes, differing in resource requirements, demand pattern, and call duration. The SP charges a fee per call, which can depend on the current congestion level, and which affects users' demand for calls. We provide a dynamic programming formulation of the problems of revenue and welfare maximization, and derive some qualitative properties of the optimal solution. We also provide a number of approximate approaches, together with an analysis that indicates that near-optimality is obtained for the case of many, relatively small, users. In particular, we show analytically as well as computationally, that the performance of an optimal pricing strategy is closely matched by a suitably chosen static price, which does not depend on instantaneous congestion. This indicates that the easily implementable time-of-day pricing will often suffice. Throughout, we compare the alternative formulations involving revenue or welfare maximization, respectively, and draw some qualitative conclusions 相似文献
2.
Stability conditions for multiclass fluid queueing networks 总被引:1,自引:0,他引:1
Bertsimas D. Gamarnik D. Tsitsiklis J.N. 《Automatic Control, IEEE Transactions on》1996,41(11):1618-1631
We introduce a new method to investigate stability of work-conserving policies in multiclass queueing networks. The method decomposes feasible trajectories and uses linear programming to test stability. We show that this linear program is a necessary and sufficient condition for the stability of all work-conserving policies for multiclass fluid queueing networks with two stations. Furthermore, we find new sufficient conditions for the stability of multiclass queueing networks involving any number of stations and conjecture that these conditions are also necessary. Previous research had identified sufficient conditions through the use of a particular class of (piecewise linear convex) Lyapunov functions. Using linear programming duality, we show that for two-station systems the Lyapunov function approach is equivalent to ours and therefore characterizes stability exactly 相似文献
3.
Polymenakos L.C. Bertsekas D.P. Tsitsiklis J.N. 《Automatic Control, IEEE Transactions on》1998,43(2):278-283
We consider a continuous space shortest path problem in a two-dimensional plane. This is the problem of finding a trajectory that starts at a given point, ends at the boundary of a compact set of ℜ 2, and minimizes a cost function of the form ∫OT r(x(t)) dt+q(x(T)). For a discretized version of this problem, a Dijkstra-like method that requires one iteration per discretization point has been developed by Tsitsiklis (1995). Here we develop some new label correcting-like methods based on the small label first methods of Bertsekas (1993) and Bertsekas et al. (1996). We prove the finite termination of these methods, and present computational results showing that they are competitive and often superior to the Dijkstra-like method and are also much faster than the traditional Jacobi and Gauss-Seidel methods 相似文献
4.
Optimal asymptotic identification under bounded disturbances 总被引:1,自引:0,他引:1
Tse D.N.C. Dahleh M.A. Tsitsiklis J.N. 《Automatic Control, IEEE Transactions on》1993,38(8):1176-1190
The intrinsic limitation of worst-case identification of linear time-invariant systems using data corrupted by bounded disturbances, when the unknown plant is known to belong to a given model set, is studied. This is done by analyzing the optimal worst-case asymptotic error achievable by performing experiments using any bounded input and estimating the plant using any identification algorithm. It is shown that under some topological conditions on the model set, there is an identification algorithm which is asymptotically optimal for any input, and the optimal asymptotic error is characterized as a function of the inputs. These results, which hold for any error metric and disturbance norm, are applied to three specific identification problems: identification of stable systems in the l 1 norm, identification of stable rational systems in the H ∞ norm and identification of unstable rational systems in the gap metric. For each of these problems, the general characterization of optimal asymptotic error is used to find near-optimal inputs to minimize the error 相似文献
5.
John N. Tsitsiklis Vincent D. Blondel 《Mathematics of Control, Signals, and Systems (MCSS)》1997,10(1):31-40
We analyze the computability and the complexity of various definitions of spectral radii for sets of matrices. We show that the joint and generalized spectral radii of two integer matrices are not approximable in polynomial time, and that two related quantities—the lower spectral radius and the largest Lyapunov exponent—are not algorithmically approximable.This work was completed while Blondel was visiting Tsitsiklis at MIT. This research was supported by the ARO under Grant DAAL-03-92-G-0115. 相似文献
6.
Efficient algorithms for globally optimal trajectories 总被引:3,自引:0,他引:3
We present serial and parallel algorithms for solving a system of equations that arises from the discretization of the Hamilton-Jacobi equation associated to a trajectory optimization problem of the following type. A vehicle starts at a prespecified point xo and follows a unit speed trajectory x(t) inside a region in ℛm until an unspecified time T that the region is exited. A trajectory minimizing a cost function of the form ∫0T r(x(t))dt+q(x(T)) is sought. The discretized Hamilton-Jacobi equation corresponding to this problem is usually solved using iterative methods. Nevertheless, assuming that the function r is positive, we are able to exploit the problem structure and develop one-pass algorithms for the discretized problem. The first algorithm resembles Dijkstra's shortest path algorithm and runs in time O(n log n), where n is the number of grid points. The second algorithm uses a somewhat different discretization and borrows some ideas from a variation of Dial's shortest path algorithm (1969) that we develop here; it runs in time O(n), which is the best possible, under some fairly mild assumptions. Finally, we show that the latter algorithm can be efficiently parallelized: for two-dimensional problems and with p processors, its running time becomes O(n/p), provided that p=O(√n/log n) 相似文献
7.
Asynchronous Stochastic Approximation and Q-Learning 总被引:21,自引:6,他引:15
We provide some general results on the convergence of a class of stochastic approximation algorithms and their parallel and asynchronous variants. We then use these results to study the Q-learning algorithm, a reinforcement learning method for solving Markov decision problems, and establish its convergence under conditions more general than previously available. 相似文献
8.
9.
Munther A. Dahleh Theodore V. Theodosopoulos John N. Tsitsiklis 《Systems & Control Letters》1993,20(3)
We consider the problem of identification of linear systems in the presence of measurement noise which is unknown but bounded in magnitude by some δ > 0. We focus on the case of linear systems with a finite impulse response. It is known that the optimal identification error is related (within a factor of 2) to the diameter of a so-called uncertainty set and that the latter diameter is upper-bounded by 2δ, if a sufficiently long identification experiment is performed. We establish that, for any K 1, the minimal length of an identification experiment that is guaranteed to lead to a diameter bounded by 2Kδ behaves like 2Nf(1/K), when N is large, where N is the length of the impulse response and is a positive function known in closed form. While the framework is entirely deterministic, our results are proved using probabilistic tools. 相似文献
10.
We study the computational complexity of the discrete versions of some simple but basic decentralized decision problems. These problems are variations of the classical "team decision problem" and include the problem of decentralized detection whereby a central processor is to select one of two hypotheses, based on l-bit messages from two noncommunicating sensors. Our results point to the inherent difficulty of decentralized decision making and suggest that optimality may be an elusive goal. 相似文献