检索结果-内蒙古大学图书馆

On the Exact Feasibility of Convex Scenario Programs With Discarded Constraints

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2023年第4期68卷 1986-2001页

作者： Romao, Licio Papachristodoulou, Antonis Margellos, Kostas Dept Comp Sci Oxford OX1 3QG England Univ Oxford Dept Engn Sci Oxford OX1 3PJ England

We revisit the so-called sampling and discarding approach used to quantify the probability of constraint violation of a solution to convex scenario programs when some of the original samples are allowed to be discarded. Motivated by two scenario programs that possess analytic solutions and the fact that the existing bound for scenario programs with discarded constraints is not tight, we analyze a removal scheme that consists of a cascade of optimization problems, where, at each step, we remove a superset of the active constraints. By relying on results from compression learning theory, we show that such a removal scheme leads to less conservative bounds for the probability of constraint violation than the existing ones. We also show that the proposed bound is tight by characterizing a class of optimization problems which achieves the given upper bound. The performance improvement of the proposed methodology is illustrated by an example that involves a resource sharing linear program.

关键词： Optimization Uncertainty Random variables Picture archiving and communication systems Costs Linear programming Algebra Chance-constrained optimization probabilistic methods randomized algorithms scenario approach

来源：评论

学校读者我要写书评

暂无评论

Finding groups with maximum betweenness centrality via integer programming with random path sampling

引用

JOURNAL OF GLOBAL OPTIMIZATION 2024年第1期88卷 199-232页

作者： Lagos, Tomas Prokopyev, Oleg A. Veremyev, Alexander Univ Pittsburgh Dept Ind Engn Pittsburgh PA 15261 USA Univ Cent Florida Dept Ind Engn & Management Syst Orlando FL 32816 USA

One popular approach to access the importance/influence of a group of nodes in a network is based on the notion of centrality. For a given group, its group betweenness centrality is computed, first, by evaluating a ratio of shortest paths between each node pair in a network that are "covered" by at least one node in the considered group, and then summing all these ratios for all node pairs. In this paper we study the problem of finding the most influential (or central) group of nodes (of some predefined size) in a network based on the concept of betweenness centrality. One known approach to solve this problem exactly relies on using a linear mixed-integer programming (linear MIP) model. However, the size of this MIP model (with respect to the number of variables and constraints) is exponential in the worst case as it requires computing all (or almost all) shortest paths in the network. We address this limitation by considering randomized approaches that solve a single linear MIP (or a series of linear MIPs) of a much smaller size(s) by sampling a sufficiently large number of shortest paths. Some probabilistic estimates of the solution quality provided by our approaches are also discussed. Finally, we illustrate the performance of our methods in a computational study.

关键词： Network analysis Group betweenness centrality randomized algorithms Sample average approximation (SAA) Linear mixed-integer programming

来源：评论

学校读者我要写书评

暂无评论

Non-additive two-option ski rental

引用

THEORETICAL COMPUTER SCIENCE 2015年 584卷 42-52页

作者： Levi, Amir Patt-Shamir, Boaz Tel Aviv Univ Sch Elect Engn IL-6997801 Tel Aviv Israel

We consider the following generalization of the classical problem of ski rental. There is a game that ends at an unknown time, and the algorithm needs to decide how to pay for the time until the game ends. In our generalization, there are two "payment plans" called "options," such that each option i (for i = 1,2) consists of two kinds of costs: b(i) is the (one time) cost to start using Option i, and a(1) is the (ongoing) usage cost per unit of time for Option i. We assume w.l.o.g. that a(1) > a(2) and b(1) < b(2). Additionally, we assume the existence of a transition cost c, which is incurred if we switch from Option 1 to Option 2. (In the classical version, b(1) = 0, a(2) = 0 and c = b(2).) We give deterministic and randomized algorithms for this general setting and analyze their competitive ratio. We also prove that the competitive ratios of our algorithms are the best possible by presenting matching lower bounds for both the deterministic and the randomized cases. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Competitive analysis Ski rental randomized algorithms Duration prediction Buy or rent

来源：评论

学校读者我要写书评

暂无评论

Online pricing for multi-type of items

引用

THEORETICAL COMPUTER SCIENCE 2015年 572卷 66-82页

作者： Ting, H. F. Xiang, Xiangzhong Univ Hong Kong Dept Comp Pokfulam Hong Kong Peoples R China

This paper studies the online pricing problem in which there is a sequence of users who want to buy items from one seller. The single seller has k types of items and each type has limited copies. These users are arriving one by one at different times and are single-minded. When arriving, each user would announce her interested bundle of items and a non-increasing acceptable price function, which specifies how much she is willing to pay for a certain number of bundles. Upon the arrival of a user, the seller needs to determine immediately the number of bundles to be sold to the user and the price he would charge her. His goal is to maximize the sum of money received from users. When items are indivisible, we show that no deterministic algorithm for the problem could have competitive ratio better than O (hk) where h is the highest unit price that at least some user is willing to pay. Thus we focus on randomized algorithms. We derive a lower bound Omega(logh + root k) on the competitive ratio of any randomized algorithm for solving this problem. Then we give the first competitive randomized algorithm Rp-MULTI which is O (psi(h)root k Delta/delta)-competitive, where Delta and delta are respectively the maximum and minimum copies a type of items can have and psi(h) is a function growing slightly faster than logh. When h is known ahead of time, the ratio is decreased to O ((logh)root k Delta/delta). When items are divisible and can be sold fractionally, we concentrate on designing competitive deterministic algorithms. We give the first competitive deterministic algorithm Dp-MULTI which is O (psi(h)root k Delta/delta)-competitive. When h is known, the ratio can be decreased to O ((logh)root k Delta/delta). We also study randomized algorithms for the problem. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Online pricing Competitive analysis Lower bounds randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Distributed Multivalued Consensus

引用

COMPUTER JOURNAL 2014年第8期57卷 1132-1140页

作者： Babaee, Arta Draief, Moez Univ London Imperial Coll Sci Technol & Med Dept Elect & Elect Engn Intelligent Syst & Networks Grp London SW7 2BT England

Motivated by the distributed binary consensus algorithm inPerron et al. [(2009) UsingThree States for Binary Consensus on Complete Graphs. INFOCOM 2009, IEEE, April, pp. 2527-2535], we propose a distributed algorithm for the multivalued consensus problem. In the multivalued consensus problem, each node initially chooses from one of k available choices and the objective of all nodes is to find the choice which was initially chosen by the majority in a distributed fashion. Although the voter model (e. g. Hassin, Y. and Peleg, D. (2002) Distributed probabilistic polling and applications to proportionate agreement. Inf. Comput., 171, 248-268) can be used to find a consensus on multiple choices, it only guarantees consensus and not the consensus on the majority. We derive the time of convergence and an upper bound for the probability of error of our proposed algorithm which shows that, similar to Perron et al. [(2009) Using Three States for Binary Consensus on Complete Graphs. INFOCOM 2009, IEEE, pp. 2527-2535], having an additional state would result in significant improvement of both the convergence time and the probability of error for complete graphs. We also show that our algorithm could be used in Erd"s-Renyi and regular graphs by simulations.

关键词： consensus distributed algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

An energy efficient ranking protocol for radio networks

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2006年第5期E89A卷 1346-1354页

作者： Nakano, Koji Hiroshima Univ Sch Engn Higashihiroshima 7398527 Japan

A radio network (RN for short) is a distributed system with no central arbiter, consisting of n radio transceivers, henceforth referred to as stations. We assume that the stations run on batteries and expends power while broadcasting/receiving a data packet. Thus, the most important measure to evaluate protocols on the radio network is the number of awake time slots, in which a station is broadcasting/receiving a data packet. We also assume that the stations are identical and have no unique ID number, and no station knows the number n of the stations. For given n keys one for each station, the ranking problem asks each station to determine the number of keys in the RN smaller than its own key. The main contribution of this paper is to present an optimal randomized ranking protocol on the k-channel RN. Our protocol solves the ranking problem, with high probability, in O(n/k + log n) time slots with every station being awake for at most O(log n) time slots. We also prove that any randomized ranking protocol is required to run in expected Omega(n/k + log n) time slots with at least one station being awake for expected Q(Iog n) time slots. Therefore, our ranking protocol is optimal.

关键词： power-aware computing adhoc networks sorting distributed algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for geometric optimization

引用

ACM COMPUTING SURVEYS 1998年第4期30卷 412-458页

作者： Agarwal, PK Sharir, M Duke Univ Dept Comp Sci Ctr Geometr Comp Durham NC 27708 USA Tel Aviv Univ Sch Math Sci IL-69978 Tel Aviv Israel NYU Courant Inst Math Sci New York NY 10012 USA

We review the recent progress in the design of efficient algorithms for various problems in geometric optimization. We present several techniques used to attack these problems, such as parametric searching, geometric alternatives to parametric searching, prune-and-search techniques for linear programming and related problems, and LP-type problems and their efficient solution. We then describe a wide range of applications of these and other techniques to numerous problems in geometric optimization, including facility location, proximity problems, statistical estimators and metrology, placement and intersection of polygons and polyhedra, and ray shooting and other query-type problems.

关键词： clustering collision detection linear programming matrix searching parametric searching proximity problems prune-and-search randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Design of a probabilistic robust track-following controller for hard disk drive servo systems

引用

MECHATRONICS 2014年第6期24卷 582-589页

作者： Chamanbaz, Mohammadreza Keikha, Ehsan Venkataramanan, Venkatakrishnan Al Mamun, Abdullah Wang, Qing-Guo A STAR Data Storage Inst Singapore Singapore Natl Univ Singapore Dept Elect & Comp Engn Singapore Singapore

This paper addresses the design of robust track-following dynamic output feedback controller for hard disk drives (HDDs) in face of parameter uncertainties which can enter into problem description in a possibly non-linear way. The design is performed in a probabilistic framework where the uncertain parameters are treated as random variables and the design specification is met with a given probability level. In particular, a sequential algorithm based on gradient iteration is employed to find a probabilistic robust feasible solution to the formulated problem. The design procedure is computationally tractable and its computational complexity does not depend on the number of uncertain parameters. Our case study allows natural frequency and damping ratio to vary within 8% and 10% from their nominal values for rigid body and all resonance modes. The designed controller achieves robustness in the presence of these uncertainties. Furthermore, the designed controller is implemented in real time on a commercial HDD. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Servo systems randomized algorithms Probabilistic robust design

来源：评论

学校读者我要写书评

暂无评论

Information measures based on fractional calculus

引用

INFORMATION PROCESSING LETTERS 2012年第23期112卷 916-921页

作者： Yu, Shiwei Huang, T-Z Liu, Xiaoyun Chen, Wufan Univ Elect Sci & Technol China Sch Automat Engn Chengdu 610054 Peoples R China Univ Elect Sci & Technol China Sch Math Sci Chengdu 610054 Peoples R China

In this letter, fractional calculus is used to propose the fractional entropy (FE) and the fractional mutual information (FMI) as the new forms of the information measure in a generalized Euclidean metric space. Being position-related and causal, FE and FMI are natural extensions and more generalized forms of Shannon entropy and mutual information, respectively. (C) 2012 Elsevier B.V. All rights reserved.

关键词： randomized algorithms Entropy Mutual information Fractional calculus

来源：评论

学校读者我要写书评

暂无评论

SUBMODULAR FUNCTION MAXIMIZATION VIA THE MULTILINEAR RELAXATION AND CONTENTION RESOLUTION SCHEMES

引用

SIAM JOURNAL ON COMPUTING 2014年第6期43卷 1831-1879页

作者： Chekuri, Chandra Vondrak, Jan Zenklusen, Rico Univ Illinois Dept Comp Sci Urbana IL 61801 USA IBM Almaden Res Ctr San Jose CA 95120 USA ETH Dept Math CH-8092 Zurich Switzerland Johns Hopkins Univ Dept Appl Math & Stat Baltimore MD 21218 USA

We consider the problem of maximizing a nonnegative submodular set function f : 2(N) -> R+ over a ground set N subject to a variety of packing-type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular, when f may be a nonmonotone function. Our algorithms are based on (approximately) maximizing the multilinear extension F of f over a polytope P that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully, it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize F over a downward-closed polytope P described by an efficient separation oracle. Previously this was known only for monotone functions. For nonmonotone functions, a constant factor was known only when the polytope was either the intersection of a fixed number of knapsack constraints or a matroid polytope. Second, we show that contention resolution schemes are an effective way to round a fractional solution, even when f is nonmonotone. In particular, contention resolution schemes for different polytopes can be combined to handle the intersection of different constraints. Via linear programming duality we show that a contention resolution scheme for a constraint is related to the correlation gap of weighted rank functions of the constraint. This leads to an optimal contention resolution scheme for the matroid polytope. Our results provide a broadly applicable framework for maximizing linear and submodular functions subject to independence constraints. We give several illustrative examples. Contention resolution schemes may find other applications.

关键词： submodular function maximization approximation algorithms randomized algorithms contention resolution

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：