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

作者： Goke, Alexander Koenemann, Jochen Mnich, Matthias Sun, Hao Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany Department of Combinatorics & Optimization University of Waterloo WaterlooONN2L 3G1 Canada

A classical branch of graph algorithms is graph transversals, where one seeks a minimum-weight subset of nodes in a node-weighted graph G which intersects all copies of subgraphs F from a fixed family Ƒ. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTASs) for planar input graphs G, using a variety of techniques like the shifting technique [B. S. Baker, J. ACM, 41 (1994), pp. 153-180], bidimensionality [F. V. Fomin et al., Bidimensionality and EPTAS, in Proceedings of SODA 2011, ACM, New York, SIAM, Philadelphia, 2011, pp. 748-759], or connectivity domination [V. Cohen-Addad et al., Approximating connectivity domination in weighted bounded-genus graphs, in Proceedings of STOC 2016, ACM, New York, 2016, pp. 584-597]. These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known. In the Even Cycle Transversal (ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini, Joret, and Pietropaoli [Hitting diamonds and growing cacti, in Proceedings of IPCO 2010, Lecture Notes in Comput. Sci. 6080, Springer, Berlin, 2010, pp. 191-204] showed that the integrality gap of the standard covering LP relaxation is Θ(log n), and that adding sparsity inequalities reduces the integrality gap to 10. Our main result is a primal-dual algorithm that yields a 47/7 ≈ 6.71-approximation for ECT on node-weighted planar graphs, and an integrality gap upper bound of the same value for the standard LP relaxation on node-weighted planar graphs. © 2022 Alexander Göke, Jochen Koenemann, Matthias Mnich, Hao Sun.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

The robust price of anarchy of altruistic games

The robust price of anarchy of altruistic games

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Models, algorithms and Technologies for Network Analysis 1

引用

丛书名： Springer Proceedings in Mathematics & Statistics

1000年

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

来源：评论

学校读者我要写书评

暂无评论

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)

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Complex network analysis of public transportation networks: A comprehensive study

Complex network analysis of public transportation networks: ...

引用

International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS)

作者： Andor Háznagy István Fi András London Tamás Nemeth Department of Highway and Railway Engineering Budapest University of Technology and Economics Department of Computational Optimization University of Szeged Department of Computer Algorithms and Artificial Intelligence University of Szeged

In this study, using the network approach, we analyzed the urban public transportation systems of 5 Hungarian cities. We performed a comprehensive network analysis of the systems with the main goal of identifying significant similarities and differences of the transportation networks of these cities. Although previous studies often investigated unweighted networks, one novelty of our study is to consider directed and weighted links, where the weights represent the capacities of the vehicles (bus, tram, trolleybus) in the morning peak hours. In particular, we calculated descriptors of global network characteristic and various centrality measures of the network nodes in both the weighted case and unweighted case. By comparing the results obtained for the different cities, we get a highly detailed picture of the differences in the organization of the public transport, which may due to historical and geographical factors. Also, by comparing the results obtained from the weighted and unweighted approaches, we can identify which are the most sensitive routes and stations of the network pointing out some organizational inconsistencies of the transportation system.

关键词： Cities and towns Vehicles Complex networks Schedules Shape

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：