John N. Tsitsiklis

Submitted to Operations Research manuscript XXXX Efficiency of Scalar-Parameterized Mechanisms (2009)

Abstract—We consider the problem of decentralized detection in failure-prone tree networks with bounded height. Specifically, we study and contrast the impact on the detection performance of either...

Error Exponents for Decentralized Detection in Tree Networks ∗ (2009)

We consider the problem of allocating a fixed amount of an infinitely divisible resource among multiple competing, fully rational users. We study the efficiency guarantees that are possible when we...

Wee Peng Tay, John N. Tsitsiklis

Summary. We consider the problem of decentralized detection in a sensor network consisting of nodes arranged as a tree of bounded height. We characterize the optimal error exponent under a...

A Structured Multiarmed Bandit Problem and the Greedy Policy (2009)

Adam J. Mersereau, Paat Rusmevichientong, John N. Tsitsiklis

We consider a multiarmed bandit problem where the expected reward of each arm is a linear function of an unknown scalar with a prior distribution. The objective is to choose a sequence of arms that...

Coordinating a Constrained Channel with Linear Wholesale Price Contracts. (2009)

Navid Sabbaghi, Yossi Sheffi, John N. Tsitsiklis

We show that when a supply channel is capacity-constrained and the constraint is tight, there is a set of linear wholesale price contracts that coordinates the channel while allowing the supplier to...

A Single-Unit Decomposition Approach to Multiechelon Inventory Systems (2009)

Alp Muharremoglu, John N. Tsitsiklis

doi 10.1287/opre.1080.0620

Parameterized Supply Function Bidding: Equilibrium and Welfare (2009)

On Krause's multi-agent consensus model with state-dependent connectivity (Extended version) (2008)

We consider a model where a finite number of producers compete to meet an infinitely divisible but inelastic demand for a product. Each firm is characterized by a production cost that is convex in...

Blondel, Vincent D., Hendrickx, Julien M., Tsitsiklis, John N.

We study a model of opinion dynamics introduced by Krause: each agent has an opinion represented by a real number, and updates its opinion by averaging all agent opinions that differ from its own by...

I. STATIC DECENTRALIZED DETECTION WITH MANY SENSORS. (2008)

November 1994 LIDS-P2275 Statistical Multiplexing of Multiple Time-Scale Markov Streams 1 (2008)

We consider a decentralized detection problem in which a number of identical sensors transmit a binary function of their observations to a fusion center which then decides which one of two...

Robert G. Gallager, John N. Tsitsiklis

We study the problem of statistical multiplexing of cell streams which have correlations at multiple time-scales. Each stream is modeled by a singularly perturbed Markovmodulated process with some...

CONVERGENCE THEORIES OF DISTRIBUTED ITERATIVE PROCESSES: A SURVEYt by (2008)

Dimitri P. Bertsekas, John N. Tsitsiklis, Michael Athans

We consider a model of distributed iterative algorithms whereby several processors participate in the computation while collecting, possibly stochastic information from the environment or other...

February 1986 LIDS-P-1478 ON STOCHASTIC SCHEDULING WITH IN-TREE PRECEDENCE CONSTRAINTS' (2008)

Abstract A SURVEY OF LARGE TIME ASYMPTOTICS OF SIMULATED ANNEALING ALGORITHMSt (2008)

We consider the problem of optimal scheduling of a set of jobs obeying in-tree precedence con-straints, when a number M of processors is available. It is assumed that the service times of different...

Simulated annealing is a probabilistic algorithm for minimizing a general cost function which may have multiple local minima. The amount of randomness in this algorithm is controlled by the...

Shie Mannor, Duncan Simester, Peng Sun, John N. Tsitsiklis

informs ® doi 10.1287/mnsc.1060.0614

Optimal Transmission Scheduling in Symmetric Communication Models with Intermittent Connectivity (2008)

We explore the properties of a congestion game in which users of a congested resource anticipate the effect of their actions on the price of the resource. When users are sharing a single resource, we...

Eytan Modiano, Senior Member, John N. Tsitsiklis

Abstract—We consider a slotted system with x queues, and independent and identically distributed (i.i.d.) Bernoulli arrivals at each queue during each slot. Each queue is associated with a channel...

A Game Theoretic View of Efficiency Loss in Resource Allocation (2008)

c ○ 1997 Kluwer Academic Publishers Rollout Algorithms for Combinatorial Optimization ∗ (2008)

Dedicated to Pravin Varaiya on the occasion of his 65th birthday Summary. Motivated by resource allocation problems in communication networks as well as power systems, we consider the design of...

Dimitri P. Bertsekas, John N. Tsitsiklis, Cynara Wu

We consider the approximate solution of discrete optimization problems using procedures that are capable of magnifying the effectiveness of any given heuristic algorithm through sequential...

CONVERGENCE RATE AND TERMINATION OF ASYNCHRONOUS ITERATIVE ALGORITHMS Abstract (2008)

Dimitri P. Bertselsas, John N. Tsitsiklis

We consider iterative algorithms of the form z:= f(z), executed by a parallel or distributed comput-ing system. We focus on asynchronous implemen-tations whereby each processor iterates on a...

CONVERGENCE RATE AND TERMINATION OF ASYNCHRONOUS ITERATIVE ALGORITHMS Abstract (2008)

Dimitri P. Bertselsas, John N. Tsitsiklis

We consider iterative algorithms of the form z:= f(z), executed by a parallel or distributed comput-ing system. We focus on asynchronous implemen-tations whereby each processor iterates on a...

ANeuro-Dynamic Programming Approach to Call Admission Control inIntegrated Service Networks: The Single Link Case 1 (2008)

Comments on “Coordination of Groups of Mobile Autonomous Agents Using Nearest Neighbor Rules” (2008)

Abstract: We formulate the call admission control problem for a single link in an integrated service environment asaMarkov Decision Problem. In principle, an optimal admission control policy can be...

Mathematical Systems Theory On the Stability of Asynchronous [terative Processes* (2008)

Abstract—We clarify the relation between the model and the convergence results of Jadbabaie et al. to those of Bertsekas et al. We show that the update equations in Jadbabaie et al. are a special...

John N. Tsitsiklis, J. N. Tsitsiklis

Abstract. We consider an iterative process in which one out of a finite set of possible operators is applied at each iteration. We obtain necessary and sufficient conditions for convergence to a...

in Several Variables. New York: Academic, 1970. A Lemma on the Multiarmed Bandit Problem (2008)

John N. Tsitsiklis, Vincent D. Blondel

[lo] R. E. Kalman, "Mathematical description of linear dynamic4 system,' ' SIAM

References (2008)

The last sentence of Corollary 2 in [TB] states that it is NP-hard to decide whether all products of two given real matrices are stable and "that this is true even if the matrices have {0,...

Multivariable Nonlinear Stochastic (2008)

Il Thomas, R. B. Stein, F. Parmipgiani, J. Vrendenbrewt, G. Rau, G. I. Zahalak, ...

J. K. Salisbury. “Active stiffness control of a manipulator in Cartesian

INTEGRAL EQUATIONS AND RESOLVENTS OF TOEPLITZ PLUS HIANKEL KERNELS* (2008)

John N. Tsitsiklis, Bernard C. Levy

Given a Fredholm integral equation with a Toeplitz plus Hankel kernel, we show that the solution may be described in terms of two coupled linear partial differential equations. These equations...

LOWER BOUNDS ON THE TIME TO COMPUTE A SIMPLE BOOLEAN FUNCTION ON A PARALLEL RANDOM ACCESS MACHINE 1 (2008)

Zhi-quan Luo, John N. Tsitsiklis, I. A Lower, Bound For, A Restricted, Class Of Algorithms

We consider a parallel random access machine (PRAM) in which information is communicated via a shared memory. We strengthen a lower bound of Cook, Dwork and Reischuk for the time required to compute...

AND (2008)

John N. Tsitsiklis, H. Papadimitriou, Pierre Humblet

Abstract. A queuing system with infinitely many servers, and with the following queuing discipline is considered: For any two jobs i and j in the system, such that i arrived later than j, there is a...

Submitted to Management Science manuscript Coordinating a Constrained Channel with Linear Wholesale Price Contracts. (2008)

Navid Sabbaghi, Yossi Sheffi, John N. Tsitsiklis

We show that when a supply channel is capacity-constrained and the constraint is tight, there is a set of linear wholesale price contracts that coordinates the channel while allowing the supplier to...

Approachability in Repeated Games: Computational Aspects and a Stackelberg Variant 1 (2008)

Optimal Transmission Scheduling in Symmetric Communication Models with Intermittent Connectivity (2008)

We consider a finite two-player zero-sum game with vector-valued rewards. We study the question of whether a given polyhedral set D is “approachable, ” that is, whether Player 1 (the “decision...

Anand Ganti Eytan, Eytan Modiano, John N. Tsitsiklis

We consider a slotted system with N queues, and i.i.d. Bernoulli arrivals at each queue during each slot. Each queue is associated with a channel that changes between "on" and "o#...

On the sub-exponential decay of detection error probabilities in long tandems (2008)

On the Nonexistence of Quadratic Lyapunov Functions for Consensus Algorithms (2008)

Abstract—We consider the problem of Bayesian decentralized binary hypothesis testing in a network of sensors arranged in a tandem. We show that the rate of error probability decay is always...

Alex Olshevsky, John N. Tsitsiklis

We provide an example proving that there exists no quadratic Lyapunov function for a certain class of linear agreement/consensus algorithms, a fact that had been numerically verified in [6]. We also...

Linearly Parameterized Bandits ∗ (2008)

Paat Rusmevichientong, John N. Tsitsiklis

We consider bandit problems involving a large (possibly infinite) collection of arms, in which the expected reward of each arm is a linear function of an r-dimensional random vector Z ∈ Rr, where r...

matrices (2007)

GRADIENT CONVERGENCE IN GRADIENT METHODS 1 (2007)

boundedness of all products of a pair of

Decision Processes (2007)

For the classical gradient method x t+1 = x t

John N. Tsitsiklis, Benjamin Van Roy, Benjamin Van Roy

in partial ful llment of the requirements for the degree of

Hidden State and Short-Term Memory: A Bibliography (2007)

Michael C. Mozer, L. Christman, John N. Tsitsiklis, The Markov, ...

sium on Theory of Computing, pages 411--420, Seattle, Washington, May 1989. [ Ross, 1970 ] S. Ross. Applied Probability Models with Optimization Applications. Holden-Day, San Francisco, Calif., 1970....

Large Deviations Bounds for Markov Decision Processes Under General Policies (2007)

We consider the empirical state-action frequencies and the empirical reward in weakly communicating finite-state Markov decision processes under general policies. We define a certain polytope and...

Complexity (2007)

Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis

of stability and controllability of elementary hybrid systems

systems (2007)

stability of saturated linear dynamical

Markov (2007)

Dimitris Bertsimas T, David Gamarnik, John N. Tsitsiklis

In this paper, we develop a systematic method for deriving bounds on the stationary distribution of stable Markov chains with a countably infinite state space. We assume that a Lyapunov function is...

The stability of saturated linear dynamical systems (2007)

Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis

is undecidable

mchp.siemens.de (2007)

Peter Marbach, Oliver Mihatsch, John N. Tsitsiklis

In integrated service communication networks, an important problem is to exercise call admission control and routing so as to optimally use the network resources. This problem is naturally formulated...

A NEURO-DYNAMIC PROGRAMMING APPROACH TO ADMISSION CONTROL IN ATM NETWORKS: THE SINGLE LINK CASE (2007)

On Average Versus, John N. Tsitsiklis, Benjamin Van Roy

We are interested in solving large-scale Markov Decision Problems. The classical method of Dynamic Programming provides a mathematical framework for finding optimal solutions for a given Markov...

March2,1999 (2007)

We provide an analytical comparison between discounted and average reward temporal-- difference (TD) learning with linearly parameterized approximations. Wefi consider the asymptotic behavior of the...

Parameterized Supply Function Bidding: Equilibrium and Welfare ∗ (2007)

Stochastic Search in a Forest Revisited (2007)

Motivated by market design for electric power systems, we consider a model where a finite number of producers compete to meet an infinitely divisible but inelastic demand for the product. Each firm...

Jay Sethuraman, John N. Tsitsiklis

Efficiency of scalar-parameterized mechanisms (2007)

On distributed averaging algorithms and quantization effects (2007)

We consider the problem of allocating a fixed amount of an infinitely divisible resource among multiple competing, fully rational users. We study the efficiency guarantees that are possible when we...

Angelia Nedić, Alex Olshevsky, Asuman Ozdaglar, John N. Tsitsiklis

We consider distributed iterative algorithms for the averaging problem over timevarying topologies. Our focus is on the convergence time of such algorithms when complete (unquantized) information is...

On the Impact of Node Failures and Unreliable Communications in Dense Sensor Networks ∗ (2007)

On the Nonexistence of Quadratic Lyapunov Functions for Consensus Algorithms (2007)

We consider the problem of decentralized detection in failure-prone tree networks with bounded height. Specifically, we study and contrast the impact on the detection performance of either node...

Alex Olshevsky, John N. Tsitsiklis

We provide an example proving that there exists no quadratic Lyapunov function for a certain class of linear agreement/consensus algorithms, a fact that had been numerically verified in [5]. We also...

Tsitsiklis. Efficiency of scalarparameterized mechanisms (2007)

Bayesian detection in bounded height tree networks (2007)

We consider the problem of allocating a fixed amount of an infinitely divisible resource among multiple competing, fully rational users. We study the efficiency guarantees that are possible when we...

Alp Muharremoglu, John N. Tsitsiklis

We study the detection performance of large scale sensor networks, configured as trees with bounded height, in which information is progressively compressed as it moves towards the root of the tree....

pp. ec1–ec10

Approachability in Repeated Games: Computational Aspects and a Stackelberg Variant 1 (2007)

A contract-based model for directed network formation (2006)

We consider a finite two-player zero-sum game with vector-valued rewards. We study the question of whether a given polyhedral set D is “approachable, ” that is, whether Player 1 (the “decision...

A robust approach to IMRT optimization (2006)

We consider a network game where the nodes of the network wish to form a graph to route traffic between themselves. We present a model where costs are incurred for routing traffic, as well as for a...

Thomas Bortfeld, John N Tsitsiklis

Parameterized Supply Function Bidding: Equilibrium and Welfare ∗ (2006)

Dynamic catalog mailing policies (2006)

Motivated by market design for electric power systems, we consider a model where a finite number of producers compete to meet an infinitely divisible but inelastic demand for the product. Each firm...

Duncan I. Simester, Peng Sun, John N. Tsitsiklis

Letters (2006)

Comment on “Coordination of Groups of Mobile Autonomous Agents Using Nearest Neighbor Rules ” ∗ (2006)

The unichain condition requires that every policy in an MDP result in a single ergodic class, and guarantees that the optimal average cost is independent of the initial state. We show that checking...

Asymptotic performance of a censoring sensor network (2006)

We clarify the relation of the model and the convergence results of Jadbabaie et al. [3] to those studied by Bertsekas et al. [6, 5, 1]. We show that the update equations in [3] are a very special...

Wee Peng Tay, Student Member, John N. Tsitsiklis, Moe Z. Win

Abstract—We consider the problem of decentralized binary detection in a sensor network where the sensors have access to side information that affects the statistics of their measurements, or...

Robust Management of Motion Uncertainty in Intensity-Modulated Radiation Therapy (2006)

Thomas Bortfeld, Alexei Trofimov, John N. Tsitsiklis

Radiation therapy is subject to uncertainties that need to be accounted for when determining a suitable treatment plan for a cancer patient. For lung and liver tumors, the presence of breathing...

When is it important to know you’ve been rejected? A search problem with probabilistic appearance of offers (2006)

Sanmay Das, John N. Tsitsiklis

A problem that often arises in the process of searching for a job or for a candidate to fill a position is that applicants do not know if they will receive an offer from any given firm with which...

Bin Packing with Queues ∗ (2006)

Devavrat Shah, John N. Tsitsiklis

We study the best achievable performance (in terms of average queue size and delay) in a stochastic and dynamic version of the bin-packing problem. Items arrive to a queue according to a Poisson...

Convergence speed in distributed consensus and averaging (2006)

Alex Olshevsky, John N. Tsitsiklis

We study the convergence speed of distributed iterative algorithms for the consensus and averaging problems, with emphasis on the latter. We first consider the case of a fixed communication topology....

Optimal transmission scheduling over a fading channel with energy and deadline constraints (2006)

Alvin Fu, Eytan Modiano, John N. Tsitsiklis

Abstract — We seek to maximize the average data throughput of a single transmitter sending data over a fading channel to a single user class. The transmitter has a fixed amount of energy and a...

Optimal transmission scheduling over a fading channel with energy and deadline constraints (2006)

Alvin Fu, Eytan Modiano, John N. Tsitsiklis

Abstract — We seek to maximize the average data throughput of a single transmitter sending data over a fading channel to a single user class. The transmitter has a fixed amount of energy and a...

Data fusion trees for detection: Does architecture matter (2006)

Wee Peng Tay, Student Member, John N. Tsitsiklis, Moe Z. Win

We consider the problem of decentralized detection in a network consisting of a large number of nodes arranged as a tree of bounded height, under the assumption of conditionally independent,...

Data fusion trees for detection: Does architecture matter (2006)

Wee Peng Tay, Student Member, John N. Tsitsiklis, Moe Z. Win

Abstract—We consider the problem of decentralized detection in a network consisting of a large number of nodes arranged as a tree of bounded height, under the assumption of conditionally...

Tsitsiklis. Convergence in multiagent coordination, consensus, and flocking (2005)

Vincent D. Blondel, Julien M. Hendrickx, Alex Olshevsky, John N. Tsitsiklis

Abstract — We discuss an old distributed algorithm for reaching consensus that has received a fair amount of recent attention. In this algorithm, a number of agents exchange their values...

Stochastic search in a forest revisited ∗ (2005)

Jay Sethuraman, John N. Tsitsiklis

We consider a generalization of the model of stochastic search in an out-forest, introduced and studied by Denardo, Rothblum, and Van der Heyden [1]. We provide a simple proof of the optimality of...

Accepted by (2005)

Randal E. Hickman, F Technology, Margaret F. Nervegna, Charles Stark, Draper Laboratory, John N. Tsitsiklis, ...

hAr\r\r I I TI · 1 rl · ·. r

Tsitsiklis. Convergence in multiagent coordination, consensus, and flocking (2005)

Vincent D. Blondel, Julien M. Hendrickx, Alex Olshevsky, John N. Tsitsiklis

Abstract — We discuss an old distributed algorithm for reaching consensus that has received a fair amount of recent attention. In this algorithm, a number of agents exchange their values...

A scalable network resource allocation mechanism with bounded efficiency loss (2005)

Efficiency Loss in Cournot Games (2005)

The design of pricing mechanisms for network resource allocation has two important objectives: 1) a simple and scalable end-to-end implementation and 2) efficiency of the resulting equilibria. Both...

Tsitsiklis. Convergence in multiagent coordination, consensus, and flocking (2005)

We consider Cournot models of competition, where market participants choose the quantities they demand or supply. We study the loss of aggregate surplus due to the exercise of market power in Cournot...

Vincent D. Blondel, Julien M. Hendrickx, Alex Olshevsky, John N. Tsitsiklis

Abstract — We discuss an old distributed algorithm for reaching consensus that has received a fair amount of recent attention. In this algorithm, a number of agents exchange their values...

Conditional Dynamics of Non-Markovian, Infinite-Server Queues (2005)

Theophane Weber, John N. Tsitsiklis, Theophane Weber

J. Spencer Standish ftreer Development Professor

Three Essays on Sequencing and Routing Problems (2005)

Agustfn Bompadre, James B. Orlin, John N. Tsitsiklis, Agustin Bompadre

2

Approachability in Repeated Games: Computational Aspects and a Stackelberg Variant 1 (2005)

The sample complexity of exploration in the multi-armed bandit problem (2004)

We consider a finite two-player zero-sum game with vector-valued rewards. We study the question of whether a given polyhedral set D is “approachable, ” that is, whether Player 1 (the “decision...

Shie Mannor, John N. Tsitsiklis, Kristin Bennett, Nicolò Cesa-bianchi

We consider the multi-armed bandit problem under the PAC (“probably approximately correct”) model. It was shown by Even-Dar et al. (2002) that given n arms, a total of O � (n/ε 2)log(1/δ) �...

Efficiency loss in market mechanisms for resource allocation (2004)

John N. Tsitsiklis, Arthur C. Smith, Ramesh Johari, Ramesh Johari

This thesis addresses a problem at the nexus of engineering, computer science, and economics: in large scale, decentralized systems, how can we efficiently allocate scarce resources among competing...

Bias and variance in value function estimation (2004)

Shie Mannor, Peng Sun, John N. Tsitsiklis

We consider the bias and variance of value function estimation that are caused by using an empirical model instead of the true model. We analyze these bias and variance for Markov processes from a...

Efficiency Loss in a Network Resource Allocation Game: The Case of Elastic Supply (2004)

Efficiency Loss in a Network Resource Allocation Game: The Case of Elastic Supply (2004)

We consider a resource allocation problem where individual users wish to send data across a network to maximize their utility, and a cost is incurred at each link that depends on the total rate sent...

On the Empirical State-Action Frequencies in Markov Decision Processes Under General Policies (2004)

We consider a resource allocation problem where individual users wish to send data across a network to maximize their utility, and a cost is incurred at each link that depends on the total rate sent...

Optimal Transmission Scheduling over a Fading Channel with Energy and Deadline Constraints (2004)

We consider the empirical state-action frequencies and the empirical reward in weakly communicating finite-state Markov decision processes under general policies. We define a certain polytope and...

Alvin Fu, Eytan Modiano, John N. Tsitsiklis

We seek to maximize the data throughput of an energy and time constrained transmitter sending data over a fading channel. The transmitter has a fixed amount of energy and a limited amount of time to...

Efficiency loss in a network resource allocation game (2004)

Efficiency loss in a network resource allocation game (2004)

Abstract—We consider a resource allocation problem where individual users wish to send data across a network to maximize their utility, and a cost is incurred at each link that depends on the total...

Tsitsiklis. Approximate gradient methods in policy-space optimization of Markov reward processes (2003)

We explore the properties of a congestion game where users of a congested resource anticipate the effect of their actions on the price of the resource. When users are sharing a single resource, we...

A Contract-Based Model for Directed Network Formation (2003)

We consider a discrete time, finite state Markov reward process that depends on a set of parameters. We start with a brief review of (stochastic) gradient descent methods that tune the parameters in...

Approximate Gradient Methods in Policy-Space Optimization of Markov Reward Processes (2003)

We consider a network game where the nodes of the network wish to form a graph to route traffic between themselves. We present a model where costs are incurred for routing traffic, as well as for a...

Tsitsiklis, “Linear Stochastic Approximation Driven by Slowly Varying (2003)

We consider a discrete time, nite state Markov reward process that depends on a set of parameters. We start with a brief review of (stochastic) gradient descent methods that tune the parameters in...

Vijay R. Konda, John N. Tsitsiklis

www.elsevier.com/locate/sysconle

Optimal energy allocation and admission control for communications satellites (2003)

Alvin C. Fu, Student Member, Eytan Modiano, Senior Member, John N. Tsitsiklis

Abstract—We address the issue of optimal energy allocation and admission control for communications satellites in earth orbit. Such satellites receive requests for transmission as they orbit the...

Dynamic Leadtime Management in Supply Chains (2003)

Tsitsiklis. Approximate gradient methods in policy-space optimization of Markov reward processes (2003)

One way to hedge against random fluctuations of demand in supply chains is to keep inventories at various points in the chain. Another is to actually modify the leadtimes in the system dynamically....

Abstract. We consider a discrete time, ®nite state Markov reward process that depends on a set of parameters. We start with a brief review of (stochastic) gradient descent methods that tune the...

Lower Bounds on the Sample Complexity of Exploration in the Multi-Armed Bandit Problem (2003)

doi 10.1287/moor.1050.0148

Transmission Scheduling for Multi-Channel Satellite and Wireless Networks,” Allerton Conference (2002)

We consider the Multi-armed bandit problem under the PAC ("probably approximately correct") model. It was shown by Even-Dar et al. [5] that given n arms, it su#ces to play the arms a total...

Eytan Modiano, John N. Tsitsiklis

We consider a slotted system with N queues, and i.i.d. Bernoulli arrivals at each queue during each slot. Each queue is associated with a beam and a channel that changes between “on ” and “off...

On the convergence of optimistic policy iteration (2002)

John N. Tsitsiklis, Sridhar Mahadevan

We consider a finite-state Markov decision problem and establish the convergence of a special case of optimistic policy iteration that involves Monte Carlo estimation of Q-values, in conjunction with...

On Differentiability of Average Cost in Parameterized Markov Chains 1 Overview (2002)

Vijay Konda, John N. Tsitsiklis, Fθ+h Fθ

The purpose of this appendix is to prove Theorem 4.6 in [5] and establish various facts used in verifying some of the assumptions of Theorem A.1 therein. We use the same notation and assumptions as...

On the Convergence of Optimistic Policy Iteration (2002)

John N. Tsitsiklis, Sridhar Mahadevan

We consider a finite-state Markov decision problem and establish the convergence of a special case of optimistic policy iteration that involves Monte Carlo estimation of Q-values, in conjunction with...

On average versus discounted reward temporal-difference learning (2002)

John N. Tsitsiklis, Benjamin Van Roy, Satinder Singh

Abstract. We provide an analytical comparison between discounted and average reward temporal-difference (TD) learning with linearly parameterized approximations. We first consider the asymptotic...

Transmission Scheduling for Multi-Channel Satellite (2002)

And Wireless Networks, Eytan Modiano, John N. Tsitsiklis

We consider a slotted system with N queues, and i.i.d. Bernoulli arrivals at each queue during each slot. Each queue is associated with a beam and a channel that changes between "on" and...

A single-unit decomposition approach to multi-echelon inventory systems (2001)

Alp Muharremoglu, John N. Tsitsiklis

We show the optimality of state dependent echelon base stock policies in uncapacitated serial inventory systems with Markov modulated demand and Markov modulated, non-order crossing stochastic...

Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions (2001)

Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis

We study the distribution of steady-state queue lengths in multiclass queueing networks under a stable policy. We propose a general methodology based on Lyapunov functions, for the performance...

Regression methods for pricing complex American-style options (2001)

Regression methods for pricing complex American-style options (2001)

We introduce and analyze a simulation-based, approximate dynamic programming method for pricing complex American-style options, with a possibly high-dimensional underlying state space. We work within...

Performance of multiclass markovian queueing networks via piecewise linear Lyapunov functions (2001)

We introduce and analyze a simulation-based, approximate dynamic programming method for pricing complex American-style options, with a possibly high-dimensional underlying state space. We work within...

Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis

We study the distribution of steady-state queue lengths in multiclass queueing networks under a stable policy. We propose a general methodology based on Lyapunov functions, for the performance...

Xilinx Inc.: XPower Tutorial: FPGA Design, XPower (2001)

Performance of multiclass markovian queueing networks via piecewise linear Lyapunov functions (2001)

Abstract. We study online learning where the objective of the decision maker is to maximize her average long-term reward given that some average constraints are satisfied along the sample path. We...

Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis

We study the distribution of steady-state queue lengths in multiclass queueing networks under a stable policy. We propose a general methodology based on Lyapunov functions for the performance...

A single-unit decomposition approach to multiechelon inventory systems. Working paper (2001)

Xilinx Inc.: XPower Tutorial: FPGA Design, XPower (2001)

We show the optimality of state dependent echelon base stock policies in uncapacitated serial inventory systems with Markov modulated demand and Markov modulated stochastic leadtimes in the absence...

Congestion-Dependent Pricing of Network Services (2000)

Abstract. We study online learning where the objective of the decision maker is to maximize her average long-term reward given that some average constraints are satisfied along the sample path. We...

Congestion-Dependent Pricing of Network Services (2000)

(submitted for publication) We consider a service provider (SP) who provides access to a communication network or some other form of on-line services. Users access the network and initiate calls that...

Call Admission Control and Routing in Integrated Service Networks Using Neuro-Dynamic Programming (2000)

(submitted for publication) We consider a service provider (SP) who provides access to a communication network or some other form of on-line services. Users access the network and initiate calls that...

Peter Marbach, Oliver Mihatsch, John N. Tsitsiklis

We consider the problem of call admission control and routing in an in tegrated services network that handles several classes of calls of dioeerent value and with dioeerent resource requirements. The...

Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard (2000)

Vincent D. Blondel, Stéphane Gaubert, John N. Tsitsiklis

The lower and average spectral radii measure respectively the minimal and average growth rates of long products of matrices taken from a nite set. The logarithm of the average spectral radius is...

A Survey of Computational Complexity Results in Systems and Control (2000)

The Boundedness of All Products of a Pair of Matrices is Undecidable (2000)

The purpose of this paper is twofold: (a) to provide a tutorial introduction to some key concepts from the theory of computational complexity, highlighting their relevance to systems and control...

Gradient-Based Optimization of Markov Reward Processes: Practical Variants (2000)

We show that the boundedness of the set of all products of a given pair # of rational matrices is undecidable. Furthermore, we show that the joint (or generalized) spectral radius #(#) is not...

The Boundedness of All Products of a Pair of Matrices Is Undecidable (2000)

We consider a discrete time, finite state Markov reward process that depends on a set of parameters. In earlier work, we proposed a class of (stochastic) gradient descent methods that tune the...

Congestion-Dependent Pricing of Network Services (2000)

We show that the boundedness of the set of all products of a given pair \Sigma of rational matrices is undecidable. Furthermore, we show that the joint (or generalized) spectral radius ae(\Sigma) is...

Submitted to IEEE Journal on Selected Areas in Communications Call Admission Control and Routing in Integrated Services Networks Using Neuro-Dynamic Programming † (1999)

Abstract—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...

Peter Marbach, Oliver Mihatsch, John N. Tsitsiklis

We consider the problem of call admission control and routing in an integrated services network that handles several classes of calls of different value and with different resource requirements. The...

Optimal Stopping of Markov Processes: Hilbert Space Theory, Approximation Algorithms, and an Application to Pricing High-Dimensional Financial Derivatives (1999)

Complexity of stability and controllability of elementary hybrid systems (1999)

We develop a theory characterizing optimal stopping times for discrete-time ergodic Markov processes with discounted rewards. The theory differs from prior work by its view of per-stage and terminal...

Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard (1999)

e consider classes of nonlinear systems that include simple hybrid systems and prove that questions related to the stability and controllability of these systems are either undecidable or...

Vincent D. Blondel, Stephane Gaubert, John N. Tsitsiklis

The lower and average spectral radii measure the minimal and average growth rates, respectively, of long products of matrices taken from a finite set. The logarithm of the average spectral radius is...

On Average Versus Discounted Reward Temporal-Difference Learning (1999)

The Complexity Of Optimal Queuing Network Control (1999)

We provide an analytical comparison between discounted and average reward temporal-difference (TD) learning with linearly parameterized approximations. We first consider the asymptotic behavior of...

Gradient Convergence In Gradient Methods With Errors (1999)

: We show that several well-known optimization problems related to the optimal control of queues are provably intractable ---independently of any unproven conjecture such as P6=NP. In particular, we...

The Stability of Saturated Linear Dynamical Systems is Undecidable (1999)

We consider the gradient method x t+1 = x t +# t (s t +w t ), where s t is a descent direction of a function f : # n # # and w t is a deterministic or stochastic error. We assume that #f is Lipschitz...

Vincent Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis

We prove that several global properties (global convergence, global asymptotic stability, mortality, and nilpotence) of particular classes of discrete time dynamical systems are undecidable. Such...

The Stability of Saturated Linear Dynamical Systems is Undecidable (1999)

Vincent Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis

mptoticallystable?),Mortality (doalltrajectoriesgo through theorigin?),andNilpotence(doesthereexistaniteratef k off such thatf k 0?). Itiswell-known thatvarioustypesofdynamicalsystems,such...

Simulation-Based Optimization of Markov Reward Processes: Implementation Issues (1999)

The Stability of Saturated Linear Dynamical Systems is Undecidable (1999)

We consider discrete time, finite state space Markov reward processes which depend on a set of parameters. Previously, we proposed a simulation-based methodology to tune the parameters to optimize...

Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis

We prove that several global properties (global convergence, global asymptotic stability, mortality, and nilpotence) of particular classes of discrete time dynamical systems are undecidable. Such...

Congestion-Dependent Pricing of On-line Internet Services (1999)

Large Deviations Analysis of the Generalized Processor Sharing Policy (1999)

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. The SP...

Dimitris Bertsimas, Ioannis Ch. Paschalidis, John N. Tsitsiklis

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...

Boundedness of Finitely Generated Matrix Semigroups is Undecidable (1999)

Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard (1999)

We show that the the boundedness of a finitely generated matrix semigroup is undecidable. Furthermore, we show that the joint (or generalized) spectral radius ae(\Sigma), associated with a finite set...

Vincent D. Blondel, Stéphane Gaubert, John N. Tsitsiklis

Abstract—The lower and average spectral radii measure, respectively, the minimal and average growth rates of long products of matrices taken from a finite set. The logarithm of the average spectral...

This work was supported by the NATO under grant CRG-961115, by (1999)

Network Alapedes, Vincent D. Blondel, John N. Tsitsiklis

� This paper was not presented at any IFAC meeting. This paper was recommended for publication in revised from by Editor M. Morari.

Brief paper Average cost temporal-di!erence learning � (1999)

Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard (1999)

presented at any IFAC meeting. This paper was recommended for

Vincent D. Blondel, Stéphane Gaubert, John N. Tsitsiklis

Abstract—The lower and average spectral radii measure, respectively, the minimal and average growth rates of long products of matrices taken from a finite set. The logarithm of the average spectral...

Large Deviations Analysis of the Generalized Processor Sharing Policy (1999)

Dimitris Bertsimas, Ioannis Ch. Paschalidis, John N. Tsitsiklis

this paper weconsider a stochastic server (modeling a multiclass communication switch) fed byaset of parallel buffers. The dynamics of the system evolve in discrete-time and the generalized processor...

The Complexity Of Optimal Queuing Network Control (1999)

Christos Papadimitriou And, Christos H. Papadimitriou, John N. Tsitsiklis

We show that several well-known optimization problems relatedtothe optimal control of queues are provably intractable ---independently of any unproven conjecture such as P6=NP. In particular, we show...

E-mail: Pascal.Koiran ens-lyon.fr (1999)

Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis

We prove that several global properties (global convergence, global asymptotic stability, mortality, and nilpotence) of particular classes of discrete time dynamical systems are undecidable. Such...

Average Cost Temporal-Difference Learning (1999)

Tsitsiklis, “The complexity of optimal queueing network control (1999)

We propose a variant of temporal-difference learning that approximates average and differential costs of an irreducible aperiodic Markov chain. Approximations are comprised of linear combinations of...

Simulation-based optimization of markov reward processes (1998)

Abstract [6,11] by reducing them to extensions of the multi-We consider the classical problem of optimal control (routing and sequencing) of a network of queues. We prove that this problem is...

Reinforcement learning for call admission control and routing in integrated service networks (1998)

Abstract: We propose a simulation-based algorithm for optimizing the average reward in a Markov Reward Process that depends on a set of parameters. As a special case, the method applies to Markov...

Peter Marbach, Oliver Mihatsch, Miriam Schulte, Zentrum Mathematik, John N. Tsitsiklis

In integrated service communication networks, an important problem is to exercise call admission control and routing so as to optimally use the network resources. This problem is naturally formulated...

Simulation-based optimization of markov reward processes (1998)

Simulation-based optimization of markov reward processes (1998)

We propose a simulation-based algorithm for optimizing the average reward in a Markov Reward Process that depends on a set of parameters. As a special case, the method applies to Markov Decision...

Deciding Stability and Mortality of Piecewise Affine Dynamical Systems (1998)

Abstract: We propose a simulation-based algorithm for optimizing the average reward in a finite-state Markov Reward Process that depends on a set of parameters. As a special case, the method applies...

Vincent D. Blondel, Olivier Bournez, Pascal Koiran, Christos H. Papadimitriou, John N. Tsitsiklis

This paper studies problems such as: given a discrete time dynamical system of the form x(t + 1) = f(x(t)) where f : R

Estimation of Time-Varying Parameters in Statistical Models; an Optimization Approach (1998)

Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis

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...

Geometric Bounds for Stationary Distributions of Infinite Markov Chains via Lyapunov Functions (1998)

Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis

In this paper, we develop a systematic method for deriving bounds on the stationary distribution of stable Markov chains with a countably infinite state space. We assume that a Lyapunov function is...

Simulation-Based Optimization of Markov Reward Processes (1998)

Simulation-Based Optimization of Markov Reward Processes (1998)

We propose a simulation-based algorithm for optimizing the average reward in a Markov Reward Process that depends on a set of parameters. As a special case, the method applies to Markov Decision...

Congestion--Dependent Pricing of Network Services (1998)

: We propose a simulation-based algorithm for optimizing the average reward in a Markov Reward Process that depends on a set of parameters. As a special case, the method applies to Markov Decision...

Ioannis Ch, Ioannis Ch. Paschalidis, John N. Tsitsiklis

We consider a service provider (SP) who provides access to a communication network or some other form of on-line services. Users access the network and initiate calls that belong to a set of diverse...

Reinforcement Learning for Call Admission Control and Routing in Integrated Service Networks (1998)

Peter Marbach, Oliver Mihatsch, Miriam Schulte, Zentrum Mathematik, John N. Tsitsiklis

In integrated service communication networks, an important problem is to exercise call admission control and routing so as to optimally use the network resources. This problem is naturally formulated...

Simulation-Based Optimization of Markov Reward Processes (1998)

Overview of Complexity and Decidability Results for Three Classes of Elementary Nonlinear Systems (1998)

We propose a simulation-based algorithm for optimizing the average reward in a Markov Reward Process that depends on a set of parameters. As a special case, the method applies to Markov Decision...

Asymptotic buffer overflow probabilities in multiclass multiplexers: An optimal control approach (1998)

It has become increasingly apparent this last decade that many problems in systems and control are NP-hard and, in some cases, undecidable. The inherent complexity of some of the most elementary...

Dimitris Bertsimas, Ioannis Ch. Paschalidis, John N. Tsitsiklis, Senior Member

Abstract—We consider a multiclass multiplexer with support for multiple service classes and dedicated buffers for each service class. Under specific scheduling policies for sharing bandwidth among...

Asymptotic buffer overflow probabilities in multiclass multiplexers: An optimal control approach (1998)

Dimitris Bertsimas, Ioannis Ch. Paschalidis, John N. Tsitsiklis

1A preliminary version of these results was reported in [BPT95]. The results in this paper are included in [Pas96]. Research supported by a Presidential Young Investigator award DDM-9158118 with...

An analysis of temporal-difference learning with function approximation (1997)

An analysis of temporal-difference learning with function approximation (1997)

We discuss the temporal-difference learning algorithm, as applied to approximating the cost-to-go function of an infinite-horizon discounted Markov chain. The algorithm weanalyze updates parameters...

Estimation of Time-Varying Parameters in Statistical Models; an Optimization Approach (1997)

We discuss the temporal-difference learning algorithm, as applied to approximating the cost-to-go function of an infinite-horizon discounted Markov chain. The algorithm we analyze updates parameters...

Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis

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...

Average Cost Temporal-Difference Learning (1997)

Complexity of Stability and Controllability of Elementary Hybrid Systems (1997)

We propose a variant of temporal--difference learning that approximates average and differential costs of an irreducible aperiodic Markov chain. Approximations are comprised of linear combinations of...

Large Deviations Analysis of the Generalized Processor Sharing Policy (1997)

this paper, we consider simple classes of nonlinear systems and prove that basic questions related to their stability and controllability are either undecidable or computationally intractable...

Dimitris Bertsimas, Ioannis Ch. Paschalidis, John N. Tsitsiklis

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...

A Neuro-Dynamic Programming Approach to Call Admission Control in Integrated Service Networks: The Single Link Case (1997)

Rollout Algorithms For Combinatorial Optimization (1997)

We formulate the call admission control problem for a single link in an integrated service environment as a Markov Decision Problem. In principle, an optimal admission control policy can be computed...

Dimitri P. Bertsekas, John N. Tsitsiklis, Cynara Wu

We consider the approximate solution of discrete optimization problems using procedures that are capable of magnifying the effectiveness of any given heuristic algorithm through sequential...

Complexity of Stability and Controllability of Elementary Hybrid Systems (1997)

When is a Pair of Matrices Mortal? (1997)

: In this paper, we consider simple classes of nonlinear systems and prove that basic questions related to their stability and controllability are either undecidable or computationally intractable...

Complexity of Stability and Controllability of Elementary Hybrid Systems (1997)

A set of matrices over the integers is said to be k-mortal (with k positive integer) if the zero matrix can be expressed as a product of length k of matrices in the set. The set is said to be mortal...

Vincent Blondel, John N. Tsitsiklis

: In this paper, we consider simple classes of nonlinear systems and prove that basic questions related to their stability and controllability are either undecidable or computationally intractable...

Asymptotic Buffer Overflow Probabilities in Multiclass Multiplexers: An Optimal Control Approach (1997)

Dimitris Bertsimas, Ioannis Ch. Paschalidis, John N. Tsitsiklis

We consider a multiclass multiplexer with support for multiple service classes, and dedicated buffers for each service class. Under specific scheduling policies for sharing bandwidth among these...

Large Deviations Analysis of the Generalized Processor Sharing Policy (1997)

Dimitris Bertsimas, Ioannis Ch. Paschalidis, John N. Tsitsiklis

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...

The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate (1997)

John N. Tsitsiklis, Vincent D. Blondel

We analyse 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...

Estimation of Time-Varying Parameters in Statistical Models; an Optimization Approach (1997)

An analysis of temporal-difference learning with function approximation (1997)

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...

Stable Linear Approximations to Dynamic Programming for Stochastic Control Problems with Local Transitions (1996)

'This research was supported by the NSF under grant ECS 9216531, EPRI under contract 8030-10, and

Benjamin Van Roy, John N. Tsitsiklis

We consider the solution to large stochastic control problems by means of methods that rely on compact representations and a variant of the value iteration algorithm to compute approximate costto-go...

Feature-based methods for large scale dynamic programming (1996)

Spectral quantities associated to pairs of matrices are hard -- when not impossible -- to compute and to approximate (1996)

We develop a methodological framework and present a few different ways in which dynamic pro-gramming and compact representations can be combined to solve large scale stochastic control problems. In...

John N. Tsitsiklis, Vincent D. Blondel

and to approximate

Stability conditions for multiclass fluid queueing networks (1996)

Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis

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...

A Neuro-Dynamic Programming Approach to Retailer Inventory Management (1996)

Benjamin Van Roy, Dimitri P. Bertsekas, Yuchun Lee, John N. Tsitsiklis

We present a model of two-echelon retailer inventory systems, and we cast the problem of generating optimal control strategies into the framework of dynamic programming. We formulate two specific...

When is a Pair of Matrices Mortal? (1996)

NP-Hardness of Some Linear Control Design Problems (1996)

A set of matrices over the integers is said to be length-k-mortal (with k positive integer) if the zero matrix can be expressed as a product of length k of matrices in the set. The set is said to be...

Vincent Blondel, John N. Tsitsiklis

We show that some basic linear control design problems are NP-hard, implying that, unless P=NP, they cannot be solved by polynomial time algorithms. The problems that we consider include simultaneous...

An Analysis of Temporal-Difference Learning with Function Approximation (1996)

Asymptotic Buffer Overflow Probabilities in Multiclass Multiplexers: An Optimal Control Approach (1996)

We discuss the temporal-difference learning algorithm, as applied to approximating the cost-to-go function of an infinite-horizon discounted Markov chain. The algorithm we analyze updates parameters...

Dimitris Bertsimas, Ioannis Ch. Paschalidis, John N. Tsitsiklis

We consider a multiclass multiplexer with support for multiple service classes, and dedicated buffers for each service class. Under specific scheduling policies for sharing bandwidth among these...

Stochastic shortest path problems with recourse (1996)

George H. Polychronopoulos, John N. Tsitsiklis

We consider shortest path problems defined on graphs with random arc costs. We assume that information on arc cost values is accumulated as the graph is being traversed. The objective is to devise a...

When is a Pair of Integer Matrices Mortal? (1995)

Blondel, Vincent, Tsitsiklis, John N.

Résumé disponible dans le fichier PDF

Efficient algorithms for globally optimal trajectories (1995)

Statistical multiplexing of multiple time-scale Markov streams (1995)

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...

Robert G. Gallager, John N. Tsitsiklis

Abstract--We study the problem of statistical multiplexing of cell streams that have correlations at multiple time-scales. Each stream is modeled by a singularly perturbed Markov-modulated process...

Statistical Multiplexing of Multiple Time-Scale Markov Streams (1995)

Robert G. Gallager, John N. Tsitsiklis

We study the problem of statistical multiplexing of cell streams which have correlations at multiple time-scales. Each stream is modeled by a singularly perturbed Markovmodulated process with some...

Worst-Case Identification of Nonlinear Fading Memory Systems (1995)

Munther A. Dahleh, Eduardo D. Sontag, John N. Tsitsiklis

In this paper, the problem of asymptotic identification for fading memory systems in the presence of bounded noise is studied. For any experiment, the worst-case error is characterized in terms of...

Worst-Case Identification of Nonlinear Fading Memory Systems (1995)

Munther A. Dahleh, Eduardo D. Sontag, John N. Tsitsiklis

In this paper, the problem of asymptotic identification for fading memory systems in the presence of bounded noise is studied. For any experiment, the worst-case error is characterized in terms of...

Worst-Case Identification of Nonlinear Fading Memory Systems (1995)

Munther A. Dahleh, Eduardo D. Sontag, John N. Tsitsiklis

In this paper, the problem of asymptotic identification for a class of fading memory systems in the presence of bounded noise is studied. For any experiment, the worst-case error is characterized in...

NP-hardness of some linear control design problems (1995)

Vincent Blonde, John N. Tsitsiklis

ABSTRACT The resulting closed loop system is We show that some basic linear control design prob-lems are NP-hard, implying that, unless P=NP, they cannot be solved by polynomial time algorithms. The...

Efficient algorithms for globally optimal trajectories (1995)

Tsitsiklis, “Worst-case identification of nonlinear fading memory systems (1995)

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...

Munther A. Dahleh, Eduardo D. Sontag, John N. Tsitsiklis

In this paper, the problem of asymptotic identification for fading memory systems in the presence of bounded noise is studied. For any experiment, the worst-case error is characterized in terms of...

Tsitsiklis, “Worst-case identification of nonlinear fading memory systems (1995)

Munther A. Dahleh, Eduardo D. Sontag, John N. Tsitsiklis

This version was never published; the published version (in Automatica, 31, no. 3, March 1995) was very summarized. In this paper, the problem of asymptotic identification for a class of fading...

The Complexity Of Optimal Queueing Network Control (1994)

On the Large Deviations Behaviour of Acyclic Networks of G/G/1 Queues (1994)

: We show that several well-known optimization problems related to the optimal control of queues are provably intractable ---independently of any unproven conjecture such as P6=NP. In particular, we...

Dimitris Bertsimas, Ioannis Ch. Paschalidis, John N. Tsitsiklis

We consider a single class, acyclic network of G/G/1 queues. We impose some mild assumptions on the service and external arrival processes and we characterize the large deviations behaviour of all...

Asynchronous Stochastic Approximation and Q-Learning (1994)

John N. Tsitsiklis, Richard Sutton

Abstract. 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...

On the large deviations behaviour of acyclic networks of G/G/1 queues (1994)

D. Bertsimas, I. Paschalidis, J. Tsitsiklis, Dimitris Bertsimas, Ioannis Ch. Paschalidis, John N. Tsitsiklis

'Research supported by a Presidential Young Investigator award DDM-9158118 with matching funds from Draper Laboratory, and by the ARO under grant DAAL-03-92-G-0115. We consider a single class,...

Optimization of multiclass queueing networks: Polyhedral and nonlinear characterizations of achievable performance (1994)

Dimitris Bertsimas, Dimitris Bertsimas, Ioannis Ch. Paschalidis, Ioannis Ch. Paschalidis, John N. Tsitsiklis, John N. Tsitsiklis

grand DAAL03-92-G0309. We consider open and closed multiclass queueing networks with Poisson arrivals (in open networks), exponentially distributed class dependent service times, and with class...

Asynchronous Stochastic Approximation and Q-Learning (1994)

simultaneous broadcasts in the hypercube * (1993)

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...

George D. Stamoulis, John N. Tsitsiklis, Communicated D. Gries

An efficient algorithm for multiple

Decentralized detection (1993)

North-Holland The sample complexity of worst-case identification of FIR linear systems * (1992)

Consider a set of sensors that receive observations from the environment and transmit finite-valued messages to a fusion center that makes a final decision on one out of M alternative hypotheses. The...

Munther A. Dahleh, Theodore V. Theodosopoulos, John N. Tsitsiklis

Abstract: We consider the problem of identification of linear systems in the presence of measurement noise which is unknown but bounded in magnitude by some 6> 0. We focus on the case of linear...

Special cases of traveling salesman and repairman problems with time windows (1992)

An analysis of stochastic shortest path problems (1991)

Consider a complete directed graph in which each arc has a given length. There is a set ofjobs, each job i located at some node of the graph, with an associated processing time hi, and whose...

On the Predictability of Coupled Automata: An Allegory About Chaos (1991)

by

Samuel R. Buss, Christos H. Papadimitriou, John N. Tsitsiklis

Abstract. We show a sharp dichotomy between systems of identical automata with a symmetric global control whose behavior is easy to predict, and those whose behavior is hard to predict. The division...

On the sub-exponential decay of detection error probabilities in long tandems,” IEEE Trans. Inf. Theory, 2007, submitted for publication. Animashree Anandkumar (S’02) received the B.Tech degree in Electrical Engineering from Indian Institute of Technology (1991)

Wee-peng Tay, John N. Tsitsiklis, Moe Z. Win

We consider the problem of Bayesian decentralized binary hypothesis testing in a network of sensors arranged in a tandem. We show that the rate of error probability decay is always sub-exponential,...

On a lower bound for the redundancy of reliable networks with noisy gates (1991)

George D. Stamoulis, John N. Tsitsiklis

We provide a proof that a logarithmic redundancy factor is necessary for the reliable computation of the parity function by means of a network with noisy gates. This is the same as the main result in...

On the Communication Complexity of Solving a Polynomial Equation (1991)

Zhi-quan Luo, John N. Tsitsiklis

LIDS-P-1876 We consider the problem of evaluating a function f(x, y) (x E sm, y E Rn) using two processors P1 and P2, assuming that processor P1 (respectively, P2) has access to input z...

On the average communication complexity of asynchronous distributed algorithms (1990)

John N. Tsitsiklis, D. Stamoulis

Abstract. We study the commumcation complexity of asynchronous distributed algorithms. Such algorithms can generate excesswely many messages in the worst case. Nevertheless, we show that, under...

A comparison of Jacobi and Gauss-Seidel parallel iterations. Applied (1989)

Convergence rate and termination of asynchronous iterative algorithms (1989)

Copyright @ 1989 Pergamon Press plc Abstract. We consider an iterative algorithm in which several components are updated in par-allel at each stage. We assume that the underlying iteration mapping is...

D. P. Bertsekas, J. N. Tsitsiklis, Dimitri P. Bertsekas, John N. Tsitsiklis

Abstract cations, it is natural to consider distributed exe-We consider iterative algorithms of the form x: = cutions of this iteration whereby the ith processor f (x), executed by a parallel or...

LIDS-P-1851 On the Communication Complexity of Distributed Algebraic Computation 1 (1989)

Zhi-quan Luo, John N. Tsitsiklis

Research supported by the ONR under contract N00014-84-K-0519 (NR 649-003) and the ARO under

A note on strategy elimination in bimatrix games (1988)

Donald E. Knuth, Christos H. Papadimitriou, John N. Tsitsiklis

In bunatrx games we study the process of successively eliminating strategies which are donunated by other-pure strategies. We show how to perform this simplification mn O(n 3) time, where n is the...

PARALLEL AND DISTRIBUTED ITERATIVE ALGORITHMS: A SELECTIVE SURVEY 1 (1988)

Communication Complexity of Convex Optimization (1987)

Due to the condition of the original material, there are unavoidable flaws in this reproduction. We have made every effort possible to provide you with the best copy available. If you are...

John N. Tsitsiklis, Zhi-quan Luo

We consider a situation where each of two processors has access to a different convex functionA, i = 1,2, defined on a common bounded domain. The proces-sors are to exchange a number of binary...

Convergence and asymptotic agreement in distributed decision problems (1984)

John N. Tsitsiklis, Michael Athans

Abstract-We consider a distributed team decision problem in nrhich A related-and much more general situation-is the subject of different agents obtain from the environment different stochastic...

Overview (1982)