Library

feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Springer
    Machine learning 35 (1999), S. 225-245 
    ISSN: 0885-6125
    Keywords: nonparametric regression ; VC dimension ; convex optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We propose a convex optimization approach to solving the nonparametric regression estimation problem when the underlying regression function is Lipschitz continuous. This approach is based on the minimization of the sum of empirical squared errors, subject to the constraints implied by Lipschitz continuity. The resulting optimization problem has a convex objective function and linear constraints, and as a result, is efficiently solvable. The estimated function computed by this technique, is proven to convergeto the underlying regression function uniformly and almost surely, when the sample size grows to infinity, thus providing a very strong form of consistency. Wealso propose a convex optimization approach to the maximum likelihood estimation of unknown parameters in statistical models, where the parameters depend continuously on some observable input variables. For a number of classical distributional forms, the objective function in the underlying optimization problem is convex and the constraints are linear. These problems are, therefore, also efficiently solvable.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 63 (1994), S. 23-45 
    ISSN: 1436-4646
    Keywords: Lagrangean relaxation ; linear programming relaxation ; polynomial algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose techniques for the solution of the LP relaxation and the Lagrangean dual in combinatorial optimization and nonlinear programming problems. Our techniques find the optimal solution value and the optimal dual multipliers of the LP relaxation and the Lagrangean dual in polynomial time using as a subroutine either the Ellipsoid algorithm or the recent algorithm of Vaidya. Moreover, in problems of a certain structure our techniques find not only the optimal solution value, but the solution as well. Our techniques lead to significant improvements in the theoretical running time compared with previously known methods (interior point methods, Ellipsoid algorithm, Vaidya's algorithm). We use our method to the solution of the LP relaxation and the Langrangean dual of several classical combinatorial problems, like the traveling salesman problem, the vehicle routing problem, the Steiner tree problem, thek-connected problem, multicommodity flows, network design problems, network flow problems with side constraints, facility location problems,K-polymatroid intersection, multiple item capacitated lot sizing problem, and stochastic programming. In all these problems our techniques significantly improve the theoretical running time and yield the fastest way to solve them.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 3
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 80 (1998), S. 63-89 
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In the last 25 years approximation algorithms for discrete optimization problems have been in the center of research in the fields of mathematical programming and computer science. Recent results from computer science have identified barriers to the degree of approximability of discrete optimization problems unless P = NP. As a result, as far as negative results are concerned a unifying picture is emerging. On the other hand, as far as particular approximation algorithms for different problems are concerned, the picture is not very clear. Different algorithms work for different problems and the insights gained from a successful analysis of a particular problem rarely transfer to another. Our goal in this paper is to present a framework for the approximation of a class of integer programming problems (covering problems) through generic heuristics all based on rounding (deterministic using primal and dual information or randomized but with nonlinear rounding functions) of the optimal solution of a linear programming (LP) relaxation. We apply these generic heuristics to obtain in a systematic way many known as well as new results for the set covering, facility location, general covering, network design and cut covering problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 60 (1993), S. 145-166 
    ISSN: 1436-4646
    Keywords: Network design ; LP relaxations ; worst-case analysis ; heuristics
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider the survivable network design problem — the problem of designing, at minimum cost, a network with edge-connectivity requirements. As special cases, this problem encompasses the Steiner tree problem, the traveling salesman problem and thek-edge-connected network design problem. We establish a property, referred to as the parsimonious property, of the linear programming (LP) relaxation of a classical formulation for the problem. The parsimonious property has numerous consequences. For example, we derive various structural properties of these LP relaxations, we present some algorithmic improvements and we perform tight worst-case analyses of two heuristics for the survivable network design problem.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 5
    Electronic Resource
    Electronic Resource
    Springer
    Queueing systems 10 (1992), S. 153-184 
    ISSN: 1572-9443
    Keywords: Transient analysis ; busy period ; transform methods ; linear algebra
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper we study the transient behavior of the MGEL/MGEM/1 queueing system, where MGE is the class of mixed generalized Erlang distributions which can approximate an arbitrary distribution. We use the method of stages combined with the separation of variables and root finding techniques together with linear and tensor algebra. We find simple closed form expressions for the Laplace transforms of the queue length distribution and the waiting time distribution under FCFS when the system is initially empty and the busy period distribution. We report computational results by inverting these expressions numerically in the time domain. Because of the simplicity of the expressions derived our algorithm is very fast and robust.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 6
    Electronic Resource
    Electronic Resource
    Springer
    Queueing systems 21 (1995), S. 337-389 
    ISSN: 1572-9443
    Keywords: Queueing networks ; loss networks ; multiarmed bandits ; bounds ; policies ; optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We survey a new approach that the author and his co-workers have developed to formulate stochastic control problems (predominantly queueing systems) asmathematical programming problems. The central idea is to characterize the region of achievable performance in a stochastic control problem, i.e., find linear or nonlinear constraints on the performance vectors that all policies satisfy. We present linear and nonlinear relaxations of the performance space for the following problems: Indexable systems (multiclass single station queues and multiarmed bandit problems), restless bandit problems, polling systems, multiclass queueing and loss networks. These relaxations lead to bounds on the performance of an optimal policy. Using information from the relaxations we construct heuristic nearly optimal policies. The theme in the paper is the thesis that better formulations lead to deeper understanding and better solution methods. Overall the proposed approach for stochastic control problems parallels efforts of the mathematical programming community in the last twenty years to develop sharper formulations (polyhedral combinatorics and more recently nonlinear relaxations) and leads to new insights ranging from a complete characterization and new algorithms for indexable systems to tight lower bounds and nearly optimal algorithms for restless bandit problems, polling systems, multiclass queueing and loss networks.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 7
    Electronic Resource
    Electronic Resource
    Springer
    Queueing systems 32 (1999), S. 319-349 
    ISSN: 1572-9443
    Keywords: large deviations ; communication networks
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper we consider a stochastic server (modeling a multiclass communication switch) fed by a set of parallel buffers. The dynamics of the system evolve in discrete-time and the generalized processor sharing (GPS) scheduling policy of [25] is implemented. The arrival process in each buffer is an arbitrary, and possibly autocorrelated, stochastic process. We obtain a large deviations asymptotic for the buffer overflow probability at each buffer. In the standard large deviations methodology, we provide a lower and a matching (up to first degree in the exponent) upper bound on the buffer overflow probabilities. We view the problem of finding a most likely sample path that leads to an overflow as an optimal control problem. Using ideas from convex optimization we analytically solve the control problem to obtain both the asymptotic exponent of the overflow probability and a characterization of most likely modes of overflow. These results have important implications for traffic management of high-speed networks. They extend the deterministic, worst-case analysis of [25] to the case where a detailed statistical model of the input traffic is available and can be used as a basis for an admission control mechanism.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 8
    Electronic Resource
    Electronic Resource
    Springer
    Queueing systems 3 (1988), S. 305-320 
    ISSN: 1572-9443
    Keywords: Multichannel queues ; mixed generalized Erlang pdf ; waiting time distribution
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A closed form expression for the waiting time distribution under FCFS is derived for the queueing system MGEk/MGEm/s, where MGEn is the class of mixed generalized Erlang probability density functions (pdfs) of ordern, which is a subset of the Coxian pdfs that have rational Laplace transform. Using the calculus of difference equations and based on previous results of the author, it is proved that the waiting time distribution is of the form 1- $$\sum\nolimits_{j = l}^{(\begin{array}{*{20}c} {s + m - l} \\ s \\ \end{array} )} {L_j e} ^{ - u_j t} $$ , under the assumption that the rootsU j are distinct, i.e. belongs to the Coxian class of distributions of order $$(\begin{array}{*{20}c} {s + m - l} \\ s \\ \end{array} )$$ . The present approach offers qualitative insight by providing exact and asymptotic expressions, generalizes and unifies the well known theories developed for the G/G/1,G/M/s systems and leads to an $$O(k^3 (\begin{array}{*{20}c} {s + m - l} \\ s \\ \end{array} )^3 )$$ algorithm, which is polynomial if only one of the parameterss orm varies, and is exponential if both parameters vary. As an example, numerical results for the waiting time distribution of the MGE2/MGE2/s queueing system are presented.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 9
    Electronic Resource
    Electronic Resource
    Springer
    Queueing systems 25 (1997), S. 115-155 
    ISSN: 1572-9443
    Keywords: non-stationary systems ; transient analysis ; Little's law ; non-homogeneous Poisson process
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper we consider the general class of non-stationary queueing models and identify structural relationships between the number of customers in the system and the delay at time t, denoted by L(t) and S(t), respectively. In particular, we first establish a transient Little's law at the same level of generality as the classical stationary version of Little's law. We then obtain transient distributional laws for overtake free non-stationary systems. These laws relate the distributions of L(t) and S(t) and constitute a complete set of equations that describes the dynamics of overtake free non-stationary queueing systems. We further extend these laws to multiclass systems as well. Finally, to demonstrate the power of the transient laws we apply them to a variety queueing systems: Infinite and single server systems with non-stationary Poisson arrivals and general non-stationary services, multiclass single server systems with general non-stationary arrivals and services, and multiserver systems with renewal arrivals and deterministic services, operating in the transient domain. For all specific systems we relate the performance measures using the established set of laws and obtain a complete description of the system in the sense that we have a sufficient number of integral equations and unknowns. We then solve the set of integral equations using asymptotic expansions and exact numerical techniques. We also report computational results from our methods.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 10
    Electronic Resource
    Electronic Resource
    Springer
    Queueing systems 31 (1999), S. 295-316 
    ISSN: 1572-9443
    Keywords: polling systems ; switch-over times ; decomposition ; distributional laws ; heavy traffic ; mixed generalized Erlang arrivals ; performance analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper we derive decomposition results for the number of customers in polling systems under arbitrary (dynamic) polling order and service policies. Furthermore, we obtain sharper decomposition results for both the number of customers in the system and the waiting times under static polling policies. Our analysis, which is based on distributional laws, relaxes the Poisson assumption that characterizes the polling systems literature. In particular, we obtain exact decomposition results for systems with either Mixed Generalized Erlang (MGE) arrival processes, or asymptotically exact decomposition results for systems with general renewal arrival processes under heavy traffic conditions. The derived decomposition results can be used to obtain the performance analysis of specific systems. As an example, we evaluate the performance of gated Markovian polling systems operating under heavy traffic conditions. We also provide numerical evidence that our heavy traffic analysis is very accurate even for moderate traffic.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...