Continuity and monotonicity of solutions to a greedy maximization problem

DOI10.1007/S00186-020-00705-XMaRDI QIDQ2216174zbMATH OpenOpenAlexFDO

Authors Łukasz Kruk

Publication date 15 December 2020

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1902.01100

zbMATH Keywords

continuityfluid modelgreedy maximizationmonotonicitypartial orderresource sharing

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Programming involving graphs or networks (90C35)

Abstract: Motivated by an application to resource sharing network modelling, we consider a problem of greedy maximization (i.e., maximization of the consecutive minima) of a vector in $R^n$, with the admissible set indexed by the time parameter. The structure of the constraints depends on the underlying network topology. We investigate continuity and monotonicity of the resulting maximizers with respect to time. Our results have important consequences for fluid models of the corresponding networks which are optimal, in the appropriate sense, with respect to handling real-time transmission requests.

Recommendations

• Parametric network utility maximization problem
• Greedy primal-dual algorithm for dynamic resource allocation in complex networks
• The Greedy Procedure for Resource Allocation Problems: Necessary and Sufficient Conditions for Optimality
• Asignacion de recuerdos max-min: Propiedades y algoritmos
• Continuous-Time Flows in Networks

Cites work

• A simplex based algorithm to solve separated continuous linear programs
• Convergence to equilibria for fluid models of FIFO queueing networks
• Convergence to equilibria for fluid models of head-of-the-line proportional processor sharing queueing networks
• Edge minimality of EDF resource sharing networks
• Ergodicity of stochastic processes describing the operation of open queueing networks
• Fluid limits for multiple-input shortest remaining processing time queues
• Fluid limits for shortest remaining processing time queues
• scientific article; zbMATH DE number 1302182 (Why is no real title available?)
• scientific article; zbMATH DE number 1502618 (Why is no real title available?)
• Minimality of EDF networks with resource sharing
• Minimax resource allocation problems: Optimization and parametric analysis
• On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models
• Real-time queues in heavy traffic with earliest-deadline-first queue discipline
• Resource sharing networks: overview and an open problem
• SRPT applied to bandwidth-sharing networks
• State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy
• State space collapse with application to heavy traffic limits for multiclass queueing networks
• Stochastic-Process Limits
• Sufficient conditions for stability of longest-queue-first scheduling: second-order properties using fluid limits

Cited in

(3)

• Parametric network utility maximization problem
• Minimal and locally edge minimal fluid models for resource-sharing networks
• Approximation for maximizing monotone non-decreasing set functions with a greedy method

This page was built for publication: Continuity and monotonicity of solutions to a greedy maximization problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2216174)