On the Multichannel Rendezvous Problem: Fundamental Limits, Optimal Hopping Sequences, and Bounded Time-to-Rendezvous
One of the fundamental problems in a cognitive radio network, known as the multichannel rendezvous problem, is for two secondary users to find a common channel that is not blocked by primary users. The basic idea for solving such a problem in most works ...
Bifurcations of Optimal Vector Fields
We study the structure of the solution set of a class of infinite-horizon dynamic programming problems with one-dimensional state spaces, as well as their bifurcations, as problem parameters are varied. The solutions are represented as the integral ...
Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
In the stochastic orienteering problem, we are given a finite metric space, where each node contains a job with some deterministic reward and a random processing time. The processing time distributions are known and independent across nodes. However the ...
Extensions of the Cavu Theorem for Repeated Games with Incomplete Information on One Side
This work is devoted to extend several asymptotic results concerning repeated games with incomplete information on one side. The model we consider is a generalization of the classical model of Aumann and Maschler Aumann et al. [Aumann RJ, Maschler M, ...
Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case
We give an algorithm for testing the extremality of minimal valid functions for Gomory and Johnson's infinite group problem that are piecewise linear possibly discontinuous with rational breakpoints. This is the first set of necessary and sufficient ...
On the Convergence of Decomposition Methods for Multistage Stochastic Convex Programs
We prove the almost-sure convergence of a class of sampling-based nested decomposition algorithms for multistage stochastic convex programs in which the stage costs are general convex functions of the decisions and uncertainty is modelled by a scenario ...
Projection: A Unified Approach to Semi-Infinite Linear Programs and Duality in Convex Programming
Fourier-Motzkin elimination is a projection algorithm for solving finite linear programs. We extend Fourier-Motzkin elimination to semi-infinite linear programs, which are linear programs with finitely many variables and infinitely many constraints. ...
Definable Zero-Sum Stochastic Games
Definable zero-sum stochastic games involve a finite number of states and action sets, and reward and transition functions, that are definable in an o-minimal structure. Prominent examples of such games are finite, semi-algebraic, or globally ...
Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints
We consider the maximization of a gross substitutes utility function under budget constraints. This problem naturally arises in applications such as exchange economies in mathematical economics and combinatorial auctions in algorithmic game theory. We ...
Full Stability in Finite-Dimensional Optimization
The paper is devoted to full stability of optimal solutions in general settings of finite-dimensional optimization with applications to particular models of constrained optimization problems, including those of conic and specifically semidefinite ...