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

IEEE International Conference on Systems, Man, and Cybernetics

作者： Kazuhei Hasegawa Masato Noto Dept. of Electrical Electronics and Information Engineering Kanagawa University

ISBN: (纸本)9781479938414

The distributed constraint optimization problem (DCOP) is known as a basic problem of multiagent systems. This problem seeks optimal solutions using cooperative behavior between agents. However, because DCOP is NP-hard, the computational load becomes massive as the number of agents increase. What are needed are high-speed algorithms that can solve problems without increasing the computational load. In recent years, methods that intentionally limit the number of cooperative agents, such as k-optimality and p-optimality, have been proposed as approximate algorithms. They are drawing attention as new approximate algorithms because they can obtain deviations from the optimal solutions. The value of optimality is an artificially established partition of state space, and there is a need to change the value for different network topologies. In this paper, we propose a method that uses swarm intelligence as a new DCOP algorithm. Each agent evaluates the state space using swarm intelligence. The available state is determined not based on values decided by each agent. Instead, a cooperative space is produced based on heuristic values to determine the optimal solutions. We also show that a new criteria of optimality can be obtained using swarm intelligence.

关键词： Particle Swarm Optimization (PSO) Distributed Constraint Optimization Problem (DCOP) Multiagent approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Revenue Maximization and Learning in Products Ranking 21

Revenue Maximization and Learning in Products Ranking

引用

Proceedings of the 22nd ACM Conference on Economics and Computation

作者： Ningyuan Chen Anran Li Shuoguang Yang University of Toronto Toronto Canada London School of Economics and Political Science London United Kingdom The Hong Kong University of Science and Technology Hong Kong Hong Kong

ISBN: (纸本)9781450385541

Online retailing has seen steady growth over the last decade. According to the Digital Commerce (formerly Internet Retailer) analysis of the US Commerce Department's year-end retail data, online sales constituted 16% of all retail sales in 2019, and is forecast to reach higher levels in the next years due to the impact of COVID-19. For an online retailer, one of the most important decisions is the products' display positioning as it plays a crucial role in shaping customers' shopping behavior. Empirical evidence abounds. Baye et al. [2] find that a consumer's likelihood of purchasing from a firm is strongly related to the order in which the firm is listed on a webpage by a search engine. In the online advertising industry, it has been widely observed that ads placed higher on a webpage attract more clicks from consumers [1]. Given the importance of product ranking positions, the key question for online retailers is how to rank the products to maximize the *** question cannot be answered definitively, unless we can characterize and quantify how exactly customers react to products ranked in different positions. There are a number of reasons to explain the so-called position bias. The first reason is the limited attention of consumers. Eyetracking experiments show that the users are less likely to examine results near the bottom of the list. Besides limited attention, a customer seems to be more likely to buy a product ranked at the top, even though there is another similar product below inside her attention span. What explains this phenomenon at the individual level? Craswell et al. [3] provide a second explanation to the position bias using experiments, which is related to the satisficing behavior of customers. In particular, the customer views product sequentially and directly proceeds to purchasing a product once the utility of the product exceeds an acceptable threshold. The remaining products in the attention span are thus never viewed. Thus, positioning

关键词： online learning online products ranking revenue maximization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Assigning tasks for efficiency in Hadoop: extended abstract 10

Assigning tasks for efficiency in Hadoop: extended abstract

引用

Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures

作者： Michael J. Fischer Xueyuan Su Yitong Yin Yale University New Haven CT USA Nanjing University Nanjing China

ISBN: (纸本)9781450300797

In recent years Google's MapReduce has emerged as a leading large-scale data processing architecture. Adopted by companies such as Amazon, Facebook, Google, IBM and Yahoo! in daily use, and more recently put in use by several universities, it allows parallel processing of huge volumes of data over cluster of machines. Hadoop is a free Java implementation of MapReduce. In Hadoop, files are split into blocks and replicated and spread over all servers in a network. Each job is also split into many small pieces called tasks. Several tasks are processed on a single server, and a job is not completed until all the assigned tasks are finished. A crucial factor that affects the completion time of a job is the particular assignment of tasks to servers. Given a placement of the input data over servers, one wishes to find the assignment that minimizes the completion time. In this paper, an idealized Hadoop model is proposed to investigate the Hadoop task assignment problem. It is shown that there is no feasible algorithm to find the optimal Hadoop task assignment unless P = NP. Assignments that are computed by the round robin algorithm inspired by the current Hadoop scheduler are shown to deviate from optimum by a multiplicative factor in the worst case. A flow-based algorithm is presented that computes assignments that are optimal to within an additive constant.

关键词： np-completeness hadoop approximation algorithm mapreduce load balancing task assignment

来源：评论

学校读者我要写书评

暂无评论

Gerrymandering Planar Graphs 24

Gerrymandering Planar Graphs

引用

Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems

作者： Jack Dippel Max Dupré la Tour April Niu Sanjukta Roy Adrian Vetta McGill University Montreal PQ Canada Pennsylvania State University & University of Leeds Leeds United Kingdom McGill Univeristy Montreal PQ Canada

ISBN: (纸本)9798400704864

We study the computational complexity of the map redistricting problem (gerrymandering). Mathematically, the electoral district designer (gerrymanderer) attempts to partition a weighted graph into k connected components (districts) such that its candidate (party) wins as many districts as possible. Prior work has principally concerned the special cases where the graph is a path or a tree. Our focus concerns the realistic case where the graph is planar. We prove that the gerrymandering problem is solvable in polynomial time in λ-outerplanar graphs, when the number of candidates and λ are constants and the vertex weights (voting weights) are polynomially bounded. In contrast, the problem is NP-complete in general planar graphs even with just two candidates. This motivates the study of approximation algorithms for gerrymandering planar graphs. However, when the number of candidates is large, we prove it is hard to distinguish between instances where the gerrymanderer cannot win a single district and instances where the gerrymanderer can win at least one district. This immediately implies that the redistricting problem is inapproximable in polynomial time in planar graphs, unless P=NP. This conclusion appears terminal for the design of good approximation algorithms - but it is not. The inapproximability bound can be circumvented as it only applies when the maximum number of districts the gerrymanderer can win is extremely small, say one. Indeed, for a fixed number of candidates, our main result is that there is a constant factor approximation algorithm for redistricting unweighted planar graphs, provided the optimal value is a large enough constant.

关键词： approximation algorithm gerrymandering planar graph redistricting social choice theory

来源：评论

学校读者我要写书评

暂无评论

An Pproximation algorithm for the Soft-Capacitated Dynamicfacility Location Problem with Penalties

An Pproximation Algorithm for the Soft-Capacitated Dynamicfa...

引用

The 2011 International Conference on Education Science and Management Engineering(ESME2011)(2011年教育科学与管理工程国际学术会议)

作者： Chunyan JIANG Basic Course Teaching Department the Armed Police AcademyLangfangChina

In this paper, we consider the Soft-Capacitated dynamic facility location problem with penalties (SCDFLPWP).We present a 3.7052-approximation primal-dual combinatorial algorithm for DFLPSP.

关键词： Dynamic facility location problem approximation algorithm submodular function

来源：评论

学校读者我要写书评

暂无评论

Edge-Disjoint Paths Revisited

引用

ACM TRANSACTIONS ON algorithmS 2007年第4期3卷 46–es页

作者： Chekuri, Chandra Khanna, Sanjeev Univ Illinois Dept Comp Sci 201 N Goodwin Ave Urbana IL 61801 USA Univ Penn Dept Comp & Informat Sci Philadelphia PA 19104 USA

The approximability of the maximum edge-disjoint paths problem (EDP) in directed graphs was seemingly settled by an Omega(m(1/2-epsilon))-hardness result of Guruswami et al. [2003], and an O(root m) approximation achievable via a natural multiconunodity-flow-based LP relaxation as well as a greedy algorithm. Here m is the number of edges in the graph. We observe that the Omega(m(1/2-epsilon))-hardness of approximation applies to sparse graphs, and hence when expressed as a function of n, that is, the number of vertices, only an Omega(n(1/2-epsilon))-hardness follows. On the other hand, O(root m)-approximation algorithms do not guarantee a sublinear (in terms of n) approximation algorithm for dense graphs. We note that a similar gap exists in the known results on the integrality gap of the flow-based LP relaxation: an Omega(root n) lower bound and O(root m) upper bound. Motivated by this discrepancy in the upper and lower bounds, we study algorithms for EDP in directed and undirected graphs and obtain improved approximation ratios. We show that the greedy algorithm has an approximation ratio of O(min(n(2/3), root m)) in undirected graphs and a ratio of O(min(n(4/5), root m)) in directed graphs. For acyclic graphs we give an O(root n ln n) approximation via LP rounding. These are the first sublinear approximation ratios for EDP. The results also extend to EDP with weights and to the uniform-capacity unsplittable flow problem (UCUFP).

关键词： Edge-disjoint paths multicommodity flow relaxation greedy algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On Approximating Constructions of Restricted Shortest Paths in Digraphs

On Approximating Constructions of Restricted Shortest Paths ...

引用

2014 International Conference on Computer,Network Security and Communication Engineering(CNSCE 2014)

作者： Jian-ping LI Hong-lin DING Wei-dong LI Department of Mathematics Yunnan University Department of Atmospheric Science Yunnan University

For a given weighted digraph D =（V, A;s, t;w, c;B）, certain stock pieces of length L and an unit price c for each stock piece, where a length function w: A → Z, a construction cost function c: A → Z0 and a constant positive integer B, we are asked to construct a path P from s to t in D, having total length ∑w（ e）≤ B, such that the arcs in P are to be cut from some stock pieces of length L, the new objective is to minimize the total cost ∑c（ e） k（ P）c where k（ P） , denotes the number of necessary stock pieces to construct the arcs in P. Moreover, we consider a special version of this problem, where c（e） =0 holds for each arc e ∈A. We design two asymptotic approximation algorithms to solve them, respectively.

关键词： Path construction Restricted shortest path Inapproximability approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient Near-optimal algorithms for Barter Exchange 17

Efficient Near-optimal Algorithms for Barter Exchange

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Zhipeng Jia Pingzhong Tang Ruosong Wang Hanrui Zhang Institute of interdisciplinary information sciences Tsinghua University

ISBN: (纸本)9781510855076

We study polynomial-time clearing algorithms for the barter exchange problem. We put forward a family of carefully designed approximation algorithms with desirable worst-case guarantees We further apply a series of novel heuristics to implement these algorithms. We demonstrate via kidney exchange data sets that these algorithms achieve near-optimal performances while outperforming the state-of-the-art ILP based algorithms in running time by orders of magnitude.

关键词： Kidney exchange approximation algorithm Experiments approximation algorithms algorithms Runtime experimentation

来源：评论

学校读者我要写书评

暂无评论

Nonlinear Discrete Optimization

引用

丛书名： Zurich lectures in advanced mathematics

2010年

作者： Shmuel Onn

ISBN: (数字)9783037195932

ISBN: (纸本)9783037190937

This monograph develops an algorithmic theory of nonlinear discrete optimization. It introduces a simple and useful setup which enables the polynomial time solution of broad fundamental classes of nonlinear combinatorial optimization and integer programming problems in variable dimension. An important part of this theory is enhanced by recent developments in the algebra of Graver bases. The power of the theory is demonstrated by deriving the first polynomial time algorithms in a variety of application areas within operations research and statistics, including vector partitioning, matroid optimization, experimental design, multicommodity flows, multi-index transportation and privacy in statistical databases. The monograph is intended for graduate students and researchers. It is accessible to anyone with standard undergraduate knowledge and mathematical maturity.

关键词： Integer programming combinatorial optimization optimization linear programming stochastic programming randomized algorithm approximation algorithm polynomial time transportation problem multi index transportation problem transshipment problem multicommodity flow congestion game spanning tree matroid submodular function matching partitioning clustering polytope zonotope edge direction totally unimodular matrix test set Graver base contingency table statistical table multiway table disclosure control data security privacy algebraic statistics experimental design Frobenius number Grobner base Hilbert scheme zero-dimensional ideal

来源：评论

学校读者我要写书评

暂无评论

Minimum Vertex Cover Problem Based on Ant Colony algorithm

Minimum Vertex Cover Problem Based on Ant Colony Algorithm

引用

The seventh Advanced Forumon Transportation of China(第七届中国交通高层论坛 AFTC'2011)

作者： Jingrong Chen Ruihua Xu School of Transportation Engineering Tongji University Shanghai 201804 China School of Mathematic School of Transportation Engineering Tongji University Shanghai 201804 China

ISBN: (纸本)9781622761227

By applying Ant-Cycle model of Ant Colony algorithm, and modifying the state transition probability, an approximation algorithm is obtained for the minimum vertex cover problem. The time complex of the algorithm is o{n2), where n is the number of vertices in a network. In the end, an example is given to illustrate the process of the algorithm.

关键词： minimum vertex cover problem Ant Colony algorithm state transition probability approximation algorithm time complex

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：