All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 39 Next

Displaying 761 – 780 of 884

Showing per page

Analysis of a near-metric TSP approximation algorithm

Sacha Krug (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

The traveling salesman problem (TSP) is one of the most fundamental optimization problems. We consider the β-metric traveling salesman problem (Δβ-TSP), i.e., the TSP restricted to graphs satisfying the β-triangle inequality c({v,w}) ≤ β(c({v,u}) + c({u,w})), for some cost function c and any three vertices u,v,w. The well-known path matching Christofides algorithm (PMCA) guarantees an approximation ratio of 3β2/2 and is the best known algorithm for the Δβ-TSP, for 1 ≤ β ≤ 2. We provide a complete...

Analysis of a non-monotone smoothing-type algorithm for the second-order cone programming

Jingyong Tang, Li Dong, Liang Fang, Li Sun (2015)

Applications of Mathematics

The smoothing-type algorithm is a powerful tool for solving the second-order cone programming (SOCP), which is in general designed based on a monotone line search. In this paper, we propose a smoothing-type algorithm for solving the SOCP with a non-monotone line search. By using the theory of Euclidean Jordan algebras, we prove that the proposed algorithm is globally and locally quadratically convergent under suitable assumptions. The preliminary numerical results are also reported which indicate...

Analysis of a two-unit standby redundant system with three states of units

Antonín Lešanovský (1982)

Aplikace matematiky

A cold-standby redundant system with two identical units and one repair facility is considered. Units can be in three states> good (I), degraded (II), and failed (III). We suppose that only the following state-transitions of a unit are possible: I → I I , I I → I I I , I I → I , I I I → I . The repair of a unit of the type I I → I can be interpreted as a preventive maintenance. Its realization depends on the states of both units. Several characteristics of the system (probabilities, distribution functions or their Laplace-Stieltjes transforms...

Analysis of an isopetype dual algorithm for optimizing control and nonlinear optimization

Wojciech Tadej, Piotr Tatjewski (2001)

International Journal of Applied Mathematics and Computer Science

First results concerning important theoretical properties of the dual ISOPE (Integrated System Optimization and Parameter Estimation) algorithm are presented. The algorithm applies to on-line set-point optimization in control structures with uncertainty in process models and disturbance estimates, as well as to difficult nonlinear constrained optimization problems. Properties of the conditioned (dualized) set of problem constraints are investigated, showing its structure and feasibility properties...

Analysis of an M|G|1|R queue with batch arrivals and two hysteretic overload control policies

Yuliya Gaidamaka, Alexander Pechinkin, Rostislav Razumchik, Konstantin Samouylov, Eduard Sopin (2014)

International Journal of Applied Mathematics and Computer Science

Hysteretic control of arrivals is one of the most easy-to-implement and effective solutions of overload problems occurring in SIP-servers. A mathematical model of an SIP server based on the queueing system M [ X ] | G | 1 ⟨ L , H ⟩ | ⟨ H , R ⟩ with batch arrivals and two hysteretic loops is being analyzed. This paper proposes two analytical methods for studying performance characteristics related to the number of customers in the system. Two control policies defined by instants when it is decided to change the system’s mode are considered....

Analysis of AQM queues with queue size based packet dropping

Andrzej Chydziński, Łukasz Chróst (2011)

International Journal of Applied Mathematics and Computer Science

Queueing systems in which an arriving job is blocked and lost with a probability that depends on the queue size are studied. The study is motivated by the popularity of Active Queue Management (AQM) algorithms proposed for packet queueing in Internet routers. AQM algorithms often exploit the idea of queue-size based packet dropping. The main results include analytical solutions for queue size distribution, loss ratio and throughput. The analytical results are illustrated via numerical examples that...

Analysis of Markov chain algorithms on spanning trees, rooted forests, and connected subgraphs

Johannes Fehrenbach, Ludger Rüschendorf (2005)

Applicationes Mathematicae

We analyse a natural edge exchange Markov chain on the set of spanning trees of an undirected graph by the method of multicommodity flows. The analysis is then refined to obtain a canonical path analysis. The construction of the flow and of the canonical paths is based on related path constructions in a paper of Cordovil and Moreira (1993) on block matroids. The estimates of the congestion measure imply a polynomial bound on the mixing time. The canonical paths for spanning trees also yield polynomial...

Analysis of M-stationary points to an EPEC modeling oligopolistic competition in an electricity spot market

René Henrion, Jiří Outrata, Thomas Surowiec (2012)

ESAIM: Control, Optimisation and Calculus of Variations

We consider an equilibrium problem with equilibrium constraints (EPEC) arising from the modeling of competition in an electricity spot market (under ISO regulation). For a characterization of equilibrium solutions, so-called M-stationarity conditions are derived. This first requires a structural analysis of the problem, e.g., verifying constraint qualifications. Second, the calmness property of a certain multifunction has to be verified in order to justify using M-stationarity conditions. Third,...

Analysis of M-stationary points to an EPEC modeling oligopolistic competition in an electricity spot market∗

René Henrion, Jiří Outrata, Thomas Surowiec (2012)

ESAIM: Control, Optimisation and Calculus of Variations

We consider an equilibrium problem with equilibrium constraints (EPEC) arising from the modeling of competition in an electricity spot market (under ISO regulation). For a characterization of equilibrium solutions, so-called M-stationarity conditions are derived. This first requires a structural analysis of the problem, e.g., verifying constraint qualifications. Second, the calmness property of a certain multifunction has to be verified in order...

Analysis of operating characteristics for the heterogeneous batch arrival queue with server startup and breakdowns

Jau-Chuan Ke, Kuo-Hsiung Wang (2003)

RAIRO - Operations Research - Recherche Opérationnelle

In this paper we consider a like-queue production system in which server startup and breakdowns are possible. The server is turned on (i.e. begins startup) when N units are accumulated in the system and off when the system is empty. We model this system by an M [ x ] /M/1 queue with server breakdowns and startup time under the N policy. The arrival rate varies according to the server’s status: off, startup, busy, or breakdown. While the server is working, he is subject to breakdowns according to a Poisson...

Analysis of Operating Characteristics for the Heterogeneous Batch Arrival Queue with Server Startup and Breakdowns

Jau-Chuan Ke, Kuo-Hsiung Wang (2010)

RAIRO - Operations Research

In this paper we consider a like-queue production system in which server startup and breakdowns are possible. The server is turned on (i.e. begins startup) when N units are accumulated in the system and off when the system is empty. We model this system by an M[x]/M/1 queue with server breakdowns and startup time under the N policy. The arrival rate varies according to the server's status: off, startup, busy, or breakdown. While the server is working, he is subject to breakdowns according to a...

Analysis of the best-worst ant system and its variants on the TSP.

Oscar Cordón, Iñaki Fernández de Viana, Francisco Herrera (2002)

Mathware and Soft Computing

In this contribution, we will study the influence of the three main components of Best-Worst Ant System: the best-worst pheromone trail update rule, the pheromone trail mutation and the restart. Both the importance of each of them and the fact whether all of them are necessary will be analyzed. The performance of different variants of this algorithm will be tested when solving different instances of the TSP.

Currently displaying 761 – 780 of 884