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

7th International Workshop on Internet and Network Economics, WINE 2011

作者： Chen, Po-An De Keijzer, Bart Kempe, David Schäfer, Guido Department of Computer Science University of Southern California United States Algorithms Combinatorics and Optimization CWI Amsterdam Netherlands Dept. of Econometrics and Operations Research VU University Amsterdam Netherlands

ISBN: (纸本)9783642255090

We study the inefficiency of equilibria for several classes of games when players are (partially) altruistic. We model altruistic behavior by assuming that player i's perceived cost is a convex combination of 1-α i times his direct cost and αi times the social cost. Tuning the parameters α i allows smooth interpolation between purely selfish and purely altruistic behavior. Within this framework, we study altruistic extensions of cost-sharing games, utility games, and linear congestion games. Our main contribution is an adaptation of Roughgarden's smoothness notion to altruistic extensions of games. We show that this extension captures the essential properties to determine the robust price of anarchy of these games, and use it to derive mostly tight bounds. © 2011 Springer-Verlag Berlin Heidelberg.

关键词： Cost effectiveness

来源：评论

学校读者我要写书评

暂无评论

On the smoothed price of anarchy of the traffic assignment problem

On the smoothed price of anarchy of the traffic assignment p...

引用

11th Workshop on Algorithmic Approaches for Transportation Modelling, optimization, and Systems, ATMOS 2011

作者： Buriol, Luciana Ritt, Marcus Rodrigues, Félix Schäfer, Guido Universidade Federal do Rio Grande do Sul Informatics Institute Theoretical Computer Science Department Brazil CWI Amsterdam Algorithms Combinatorics and Optimization Group VU University Amsterdam Department of Econometrics and Operations Research Netherlands

ISBN: (纸本)9783939897330

We study the effect of perturbations on the Price of Anarchy for the Traffic Assignment Problem. Adopting the smoothed analysis approach, we randomly perturb the latency functions of the given network and estimate the expected Price of Anarchy on the perturbed instances. We provide both theoretical and experimental results that show that the Smoothed Price of Anarchy is of the same order of magnitude as the original one. © Luciana Buriol, Marcus Ritt, Félix Rodrigues, Guido Schäfer.

关键词： Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

GRASP with path-relinking for the quadratic assignment problem

引用

3rd International Workshop on Experimental and Efficient algorithms, WEA 2004

作者： Oliveira, Carlos A. S. Pardalos, Panos M. Resende, Mauricio G. C. Department of Industrial and Systems Engineering University of Florida 303 Weil Hall GainesvilleFL32611 United States Algorithms and Optimization Research Department AT and T Labs Research 180 Park Avenue Florham ParkNJ07932 United States

ISBN: (纸本)3540220674

This paper describes a GRASP with path-relinking heuristic for the quadratic assignment problem. GRASP is a multi-start procedure, where different points in the search space are probed with local search for high-quality solutions. Each iteration of GRASP consists of the construction of a randomized greedy solution, followed by local search, starting from the constructed solution. Path-relinking is an approach to integrate intensification and diversification in search. It consists in exploring trajectories that connect high-quality solutions. The trajectory is generated by introducing in the initial solution, attributes of the guiding solution. Experimental results illustrate the effectiveness of GRASP with path-relinking over pure GRASP on the quadratic assignment problem. © Springer-Verlag Berlin Heidelberg 2004.

关键词： Local search (optimization)

来源：评论

学校读者我要写书评

暂无评论

Models, algorithms and Technologies for Network Analysis 1

引用

丛书名： Springer Proceedings in Mathematics & Statistics

1000年

作者： Mikhail V. Batsyn Valery A. Kalyagin Panos M. Pardalos

来源：评论

学校读者我要写书评

暂无评论

Problems on Group-Labeled Matroid Bases 51

Problems on Group-Labeled Matroid Bases

引用

51st International Colloquium on Automata, Languages, and Programming, ICALP 2024

作者： Hörsch, Florian Imolay, András Mizutani, Ryuhei Oki, Taihei Schwarcz, Tamás Algorithms and Complexity Group CISPA Saarbrücken Germany MTA-ELTE Matroid Optimization Research Group Department of Operations Research ELTE Eötvös Loránd University Budapest Hungary Department of Mathematical Informatics Graduate School of Information Science and Technology The University of Tokyo Japan

ISBN: (纸本)9783959773225

Consider a matroid equipped with a labeling of its ground set to an abelian group. We define the label of a subset of the ground set as the sum of the labels of its elements. We study a collection of problems on finding bases and common bases of matroids with restrictions on their labels. For zero bases and zero common bases, the results are mostly negative. While finding a non-zero basis of a matroid is not difficult, it turns out that the complexity of finding a non-zero common basis depends on the group. Namely, we show that the problem is hard for a fixed group if it contains an element of order two, otherwise it is polynomially solvable. As a generalization of both zero and non-zero constraints, we further study F-avoiding constraints where we seek a basis or common basis whose label is not in a given set F of forbidden labels. Using algebraic techniques, we give a randomized algorithm for finding an F-avoiding common basis of two matroids represented over the same field for finite groups given as operation tables. The study of F-avoiding bases with groups given as oracles leads to a conjecture stating that whenever an F-avoiding basis exists, an F-avoiding basis can be obtained from an arbitrary basis by exchanging at most |F| elements. We prove the conjecture for the special cases when |F| ≤ 2 or the group is ordered. By relying on structural observations on matroids representable over fixed, finite fields, we verify a relaxed version of the conjecture for these matroids. As a consequence, we obtain a polynomial-time algorithm in these special cases for finding an F-avoiding basis when |F| is fixed. © Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki, and Tamás Schwarcz.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Models, algorithms and Technologies for Network Analysis 1

引用

丛书名： Springer Proceedings in Mathematics & Statistics

1000年

作者： Valery A. Kalyagin Petr A. Koldanov Panos M. Pardalos

ISBN: (数字)9783319296081

ISBN: (纸本)9783319296067;9783319806075

The contributions in this volume cover a broad range of topics including maximum cliques, graph coloring, data mining, brain networks, Steiner forest, logistic and supply chain networks. Network algorithms and their applications to market graphs, manufacturing problems, internet networks and social networks are highlighted. The "Fourth International Conference in Network Analysis," held at the Higher School of Economics, Nizhny Novgorod in May 2014, initiated joint research between scientists, engineers and researchers from academia, industry and government; the major results of conference participants have been reviewed and collected in this Work. researchers and students in mathematics, economics, statistics, computer science and engineering will find this collection a valuable resource filled with the latest research in network analysis.

关键词： algorithms Combinatorics Operations research, Management Science

来源：评论

学校读者我要写书评

暂无评论

Market graph construction using the performance measure of similarity 1

引用

3rd International Conference on Network Analysis, Net 2013

作者： Glotov, Andrey A. Kalyagin, Valery A. Vizgunov, Arsenii N. Pardalos, Panos M. National Research University Higher School of Economics 25/12 Bolshaja Pecherskaja Ulitsa Nizhny Novgorod603155 Russia Laboratory of Algorithms and Technologies for Networks Analysis Department of Applied Mathematics and Informatics National Research University Higher School of Economics Nizhny Novgorod603155 Russia Department of Industrial and Systems Engineering Center for Applied Optimization University of Florida GainesvilleFL32608 United States Laboratory of Algorithms and Technologies for Networks Analysis National Research University Higher School of Economics Nizhny Novgorod603155 Russia

ISBN: (数字)9783319097589

ISBN: (纸本)9783319097572

The paper presents the description of the modification of the stock market graph model. Authors suggest a new similarity measure between stocks. Following the market graph model a vertex represents a stock. For each pair of stocks we calculate a number of weeks when both stocks were profitable simultaneously. This number is used as a weight of edge between two vertices. The structural properties of the graph constructed by means of the suggested measure can be used to evaluate potential profitability, performance of the stock market. The model was applied to Russian stock market and to US stock market for the time period from 2001 to 2011. The main result of the analysis is the description of the peculiarity of the Russian stock market comparing with the well-developed US stock market and observation that constructed US stock market graph follows the power law model. © Springer International Publishing Switzerland 2014.

关键词： Financial markets

来源：评论

学校读者我要写书评

暂无评论

A hybrid metaheuristic for routing on multicast networks 1

引用

3rd International Conference on Network Analysis, Net 2013

作者： Oliveira, Carlos A. S. Pardalos, Panos M. Quantitative Research Dept. F-Squared Inc PrincetonNJ United States Department of Industrial and Systems Engineering Center for Applied Optimization University of Florida GainesvilleFL32608 United States Laboratory of Algorithms and Technologies for Networks Analysis National Research University Higher School of Economics Nizhny Novgorod603155 Russia

ISBN: (数字)9783319097589

ISBN: (纸本)9783319097572

Multicast routing systems have the objective of simultaneously transferring data to multiple destination nodes while using a single "push" operation. This leads to cost savings associated with reduced bandwidth utilization, which results from a decrease in data duplication across network links. An important problem on multicast networks, known as the delay constrained multicast routing problem (DCMRP), asks for the determination of an optimal route for packet transfers between members of a multicast group. Several heuristics have been proposed in the last few years to solve the DCMRP, which is of great interest for telecommunication engineers. In this paper we propose a novel, hybrid metaheuristic approach for the DCMRP, where a greedy randomized adaptive search procedure is used along with variable neighborhood search algorithm to find near optimal solutions. Computational experiments show that the proposed technique provides superior solution quality, while it is also efficient in terms of the use of computational resources. © Springer International Publishing Switzerland 2014.

关键词： optimization

来源：评论

学校读者我要写书评

暂无评论

TSP cuts which do not conform to the template paradigm 5th

引用

5th International Conference on Mobile Agents, MA 2001

作者： Applegate, David Bixby, Robert Chvátal, Vašek Cook, William Algorithms and Optimization Department AT and T Labs – Research Florham ParkNJ07932 United States Computational and Applied Mathematics Rice University HoustonTX77005 United States Department of Computer Science Rutgers University PiscatawayNJ08854 United States Program in Applied and Computational Mathematics Princeton University PrincetonNJ08544 United States

ISBN: (纸本)3540428771

The first computer implementation of the Dantzig-Fulkerson- Johnson cutting-plane method for solving the traveling salesman problem, written by Martin, used subtour inequalities as well as cutting planes of Gomory’s type. The practice of looking for and using cuts that match prescribed templates in conjunction with Gomory cuts was continued in computer codes of Miliotis, Land, and Fleischmann. Gr¨otschel, Padberg, and Hong advocated a different policy, where the template paradigm is the only source of cuts;furthermore, they argued for drawing the templates exclusively from the set of linear inequalities that induce facets of the TSP polytope. These policies were adopted in the work of Crowder and Padberg, in the work of Gr¨otschel and Holland, and in the work of Padberg and Rinaldi;their computer codes produced the most impressive computational TSP successes of the nineteen eighties. Eventually, the template paradigm became the standard frame of reference for cutting planes in the TSP. The purpose of this paper is to describe a technique for finding cuts that disdains all understanding of the TSP polytope and bashes on regardless of all prescribed templates. Combining this technique with the traditional template approach was a crucial step in our solutions of a 13,509-city TSP instance and a 15,112-city TSP instance. © Springer-Verlag Berlin Heidelberg 2001.

关键词： Traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

2.5-connectivity: Unique components, critical graphs, and applications

arXiv

引用

arXiv 2020年

作者： Heinrich, Irene Heller, Till Schmidt, Eva Streicher, Manuel Algorithms and Complexity Group Department of Computer Science Technische Universität Kaiserslautern Kaiserslautern Germany Department of Optimization Fraunhofer ITWM Kaiserslautern Germany Optimization Research Group Department of Mathematics Technische Universität Kaiserslautern Kaiserslautern Germany

If a 2-connected graph stays connected after the removal of an arbitrary vertex and an arbitrary edge, then it is called 2.5-connected. We prove that every 2-connected graph has a canonical decomposition into 2.5-connected components. These components are arranged in a treestructure. We also discuss the connection between 2.5-connected components and triconnected components and use this to present a linear time algorithm which computes the 2.5-connected components of a graph. We show that every critical 2.5-connected graph other than K4 can be obtained from critical 2.5-connected graphs of smaller order using simple graph operations. Furthermore, we demonstrate applications of 2.5-connected components in the context of cycle decompositions and cycle *** Codes 05C40, 05C45, 05C85, 05C75 Copyright © 2020, The Authors. All rights reserved.

关键词： Clustering algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：