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

10th Annual Computing and Communication Workshop and Conference (CCWC)

作者： Kamura, Yuusaku Tokyo Online Univ Joint Res Lab Tokyo Japan

ISBN: (纸本)9781728137834

In this study, we deal with the vector case's bottleneck assignment problem. Each edge's cost is introduced by the sum of the vertices which are assigned. This problem is NP-complete. We show an idea that we use a clustering method to divide the problem to partial ones. Each vertices' set is divided into subsets by a non-hierarchical clustering method. We make the optimal combination of the subsets, then vertices in the subset are corresponded according to the subsets' combinations. We examine our proposed algorithm in effectiveness by numerical experiments.

关键词： Optimization Assignment problem Combinatorial problem approximation algorithm Clustering method

来源：评论

学校读者我要写书评

暂无评论

A Primal-Dual algorithm for Euclidean k-Means Problem with Penalties 16th

A Primal-Dual Algorithm for Euclidean k-Means Problem with P...

引用

16th International Conference on Theory and Applications of Models of Computation (TAMC)

作者： Ren, Chunying Xu, Dachuan Du, Donglei Li, Min Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Univ New Brunswick Fac Management Fredericton NB E3B 5A3 Canada Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China

ISBN: (纸本)9783030592660;9783030592677

In the classical k-means problem, we are given a data set D subset of R-l and an integer k. The object is to select a set S subset of R-l of size at most k such that each point in D is connected to the closet cluster in S with minimum total squared distances. However, in some real-life applications, it is more desirable and beneficial to pay a small penalty for not connecting some outliers in D that are too far away from most points. As a result, we are motivated to study the k-means problem with penalties, for which we propose a (6.357+epsilon)-approximation algorithm via the primal-dual technique, improving the previous best approximation ratio of 19.849 + is an element of in [7] also by using the primal-dual technique.

关键词： approximation algorithm k-means problem Penalties Primal-dual

来源：评论

学校读者我要写书评

暂无评论

Geodemographic Influence Maximization 20

Geodemographic Influence Maximization

引用

26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)

作者： Zhang, Kaichen Zhou, Jingbo Tao, Donglai Karras, Panagiotis Li, Qing Xiong, Hui Baidu Res Business Intelligence Lab Beijing Peoples R China Aarhus Univ Aarhus Denmark Baidu Inc Beijing Peoples R China Natl Engn Lab Deep Learning Technol & Applicat Beijing Peoples R China Beijing Univ Posts & Telecommun Beijing Peoples R China Tsinghua Univ Beijing Peoples R China Rutgers State Univ Newark NJ 07103 USA Baidu Res Beijing Peoples R China

ISBN: (纸本)9781450379984

Given a set of locations in a city, on which ones should we place ads on so as to reach as many people as possible within a limited budget? Past research has addressed this question under the assumption that dense trajectory data are available to determine the reach of each ad. However, the data that are available in most industrial settings do not consist of dense, long-range trajectories;instead, they consist of statistics on people's short-range point-to-point movements. In this paper, we address the natural problem that arises on such data: given a distribution of population and point-to-point movement statistics over a network, find a set of locations within a budget that achieves maximum expected reach. We call this problem geodemographic influence maximization (GIM). We show that the problem is NP-hard, but its objective function is monotone and submodular, thus admits a greedy algorithm with a 1/2(1 - 1/e) approximation ratio. Still, this algorithm is inapplicable on large-scale data for high-frequency digital signage ads. We develop an efficient deterministic algorithm, Lazy-Sower, exploiting a novel, tight double-bounding scheme of marginal influence gain as well as the locality proprieties of the problem;a learning-based variant, NN-Sower, utilizes randomization and deep learning to further improve efficiency, with a slight loss of quality. Our exhaustive experimental study on two real-world urban datasets demonstrates the efficacy and efficiency of our solutions compared to baselines.

关键词： neural network influence maximization geodemographic influence submodular optimization approximation algorithm outdoor advertising

来源：评论

学校读者我要写书评

暂无评论

Sorting by Reversals and Transpositions with Proportion Restriction 1

引用

Brazilian Symposium on Bioinformatics (BSB)

作者： Brito, Klairton Lima Alexandrino, Alexsandro Oliveira Oliveira, Andre Rodrigues Dias, Ulisses Dias, Zanoni Univ Estadual Campinas Inst Comp Campinas Brazil Univ Estadual Campinas Sch Technol Limeira Brazil

ISBN: (数字)9783030657758

ISBN: (纸本)9783030657741;9783030657758

In the field of comparative genomics, one way of comparing two genomes is through the analysis of how they distinguish themselves based on a set of mutations called rearrangement events. When considering that genomes undergo different types of rearrangements, it can be assumed that some events are more common than others. To model this assumption one can assign different weights to different events, where more common events tend to cost less than others. However, this approach, called weighted, does not guarantee that the rearrangement assumed to be the most frequent will be also the most frequently returned by proposed algorithms. To overcome this issue, we investigate a new problem where we seek the shortest sequence of rearrangement events able to transform one genome into the other, with a restriction regarding the proportion between the events returned. Here we consider two rearrangement events: reversal, that inverts the order and the orientation of the genes inside a segment of the genome, and transposition, that moves a segment of the genome to another position. We present an approximation algorithm applicable to any desired proportion, for both scenarios where the orientation of the genes is known or unknown. We also show an improved (asymptotic) approximation algorithm for the case where the gene orientation is known.

关键词： Rearrangement events Proportion restriction approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Better approximations for General Caching and UFP-Cover Under Resource Augmentation 37

Better Approximations for General Caching and UFP-Cover Unde...

引用

37th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Cristi, Andres Wiese, Andreas Univ Chile Santiago Chile

ISBN: (纸本)9783959771405

In the Unsplittable Flow on a Path Cover (UFP-cover) problem we are given a path with a demand for each edge and a set of tasks where each task is defined by a subpath, a size and a cost. The goal is to select a subset of the tasks of minimum cost that together cover the demand of each edge. This problem models various resource allocation settings and also the general caching problem. The best known polynomial time approximation ratio for it is 4 [Bar-Noy et al., STOC 2000]. In this paper, we study the resource augmentation setting in which we need to cover only a slightly smaller demand on each edge than the compared optimal solution. If the cost of each task equals its size (which represents the natural bit-model in the related general caching problem) we provide a polynomial time algorithm that computes a solution of optimal cost. We extend this result to general caching and to the packing version of Unsplittable Flow on a Path in their respective natural resource augmentation settings. For the case that the cost of each task equals its "area", i.e., the product of its size and its path length, we present a polynomial time (1 + epsilon)-approximation for UFP-cover. If additionally the edge capacities are in a constant range we compute even a solution of optimal cost and also obtain a PTAS without resource augmentation.

关键词： General caching unsplittable flow cover approximation algorithm resource augmentation

来源：评论

学校读者我要写书评

暂无评论

Covering Users by a Connected Swarm Efficiently 1

引用

16th International Symposium on algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS)

作者： Danilchenko, Kiril Segal, Michael Nutov, Zeev Ben Gurion Univ Negev Sch Elect & Comp Engn Beer Sheva Israel Open Univ Israel Raanana Israel

ISBN: (数字)9783030624019

ISBN: (纸本)9783030624002;9783030624019

In this paper we study covering problems that arise in wireless networks with Unmanned Aerial Vehicles (UAVs) swarms. In the general setting we want to place a set of UAVs that should cover a given set of planar users under some constraints and we want to maintain the solution efficiently in a static and dynamic fashion. Specifically, for a set S of n non-negative weighted points in the plane, we consider a set P of m disks (or squares) of radius RCOV where the goal is to place (and maintain under dynamic updates) their location such that the sum of the weights of the points in S covered by disks from P is maximized. In the connected version, we also require that the graph imposed on P should be connected. Moreover, for the static connected version we improve the results from [1] and we obtain a constant factor approximation algorithm. In order to solve our problem under various requirements, we use a variety of techniques including dynamic grid, a reduction to Budgeted Subset Steiner Connected Dominating Set problem, tree partition, and others. We present several simple data structures that maintain an O(1)-approximate solution efficiently, under insertions and deletions of points to/from S where each update operation can be performed in logarithmic time.

关键词： Budgeted covering approximation algorithm Dynamic data structure Tree partition

来源：评论

学校读者我要写书评

暂无评论

Optimization Approaches for Mobility and Service Sharing

Optimization Approaches for Mobility and Service Sharing

引用

作者： Yu, Miao University of Michigan

学位级别：Ph.D.

Mobility and service sharing is undergoing a fast rise in popularity and industrial growth in recent years. For example, in patient-centered medical home care, services are delivered to patients at home, who share a group of medical staff riding together in a vehicle that also carries shared medical devices; companies such as Amazon and Meijer have been investing tremendous human effort and money in grocery delivery to customers who share the use of delivery vehicles and staff. In such mobility and service sharing systems, decision-makers need to make a wide range of system design and operational decisions, including locating service facilities, matching supplies with demand for shared mobility services, dispatching vehicles and staff, and scheduling appointments. The complexity of the linking decisions and constraints, as well as the dimensionality of the problems in the real world, pose challenges in finding optimal strategies efficiently. In this work, we apply techniques from Operations Research to investigate the optimal and practical solution approaches to improve the quality of service, cost-effectiveness, and operational efficiency of mobility and service sharing in a variety of applications. We deploy stochastic programming, integer programming, and approximation algorithms to address the issues in decision-making for seeking fast and reliable solutions for planning and operations problems. This dissertation contains four main chapters. In Chapter 2, we consider a class of vehicle routing problems (VRPs) where the objective is to minimize the longest route taken by any vehicle as opposed to the total distance of all routes. In such a setting, the traditional decomposition approach fails to solve the problem effectively. We investigate the hardness result of the problem and develop an approximation algorithm that achieves the best approximation ratio. In Chapter 3, we focus on developing an efficient computational algorithm for the elementary shortest path p

关键词： Mobility and Service Sharing Vehicle Routing approximation algorithm Stochastic Programming Optimization Operations Research Thesis

来源：评论

学校读者我要写书评

暂无评论

Data science for social good - Theory and applications in epidemics, polarization, and fair clustering

Data science for social good - Theory and applications in ep...

引用

作者： Xiao, Han Aalto University

学位级别：博士

Technical innovations have transformed our lives fundamentally, in both positive and negative ways. In this thesis, we look at the negative side. We identify three problems to tackle, namely epidemics, online polarization, and bias in automatic decision-making processes, and approach them using data-driven approaches. Thanks to globalization, our world is more interconnected than before. While trade and exchange of ideas are happening at an unprecedented rate, the rapid spread of disease is happening globally, as evidenced by the pandemic of COVID-19. To contain epidemics effectively, it is crucial to identify as many infected persons as possible. In practice, however, it is almost impossible to obtain the complete information of who is infected. We study this challenge in the context of social networks, where a disease spreads via network edges. Specifically, we assume only a subset of all infections is observed and we seek to infer who else is infected. Furthermore, we consider two different settings: (1) temporal setting, in which infection time is also observed and, (2) probabilistic setting, in which infection probability of each individual is ***-media platforms enable people to share and access information easily. Meanwhile, flawed designs in these platforms contribute to the formation of online polarization. As a result, people are unlikely to adopt new ideas that differ from their beliefs, which finally leads to a polarized society. To tackle online polarization, we argue that it is important to discover who is involved in the polarization. We consider a problem setting under social networks, in which the interaction between two persons is either friendly or antagonistic. Furthermore, given some seed nodes that represent different sides of a polarized subgraph, we seek to find the polarized subgraph that is relevant to the seeds. Finding such structures can be used to understand the nature of polarization, and to mitigate the degree of polariza

关键词： data mining graph mining social network analysis epidemics fairness online polarization algorithm design approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for visibility computation and testing over a terrain

引用

APPLIED GEOMATICS 2017年第1期9卷 53-59页

作者： Alipour, Sharareh Ghodsi, Mohammad Gudukbay, Ugur Golkari, Morteza Sharif Univ Technol Dept Comp Engn Tehran Iran Inst Res Fundamental Sci IPM Tehran Iran Bilkent Univ Dept Comp Engn Ankara Turkey

Given a 2.5D terrain and a query point p on or above it, we want to find the triangles of terrain that are visible from p. We present an approximation algorithm to solve this problem. We implement the algorithm and test it on real data sets. The experimental results show that our approximate solution is very close to the exact solution and compared to the other similar works, the computational cost of our algorithm is lower. We analyze the computational complexity of the algorithm. We consider the visibility testing problem where the goal is to test whether a given triangle of the terrain is visible or not with respect to p. We present an algorithm for this problem and show that the average running time of this algorithm is the same as the running time of the case where we want to test the visibility between two query points p and q. We also propose a randomized algorithm for providing an estimate of the portion of the visible region of a terrain for a query point.

关键词： Visibility computation Visibility counting problem Visibility testing problem approximation algorithm Randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Reversals and transpositions distance with proportion restriction

引用

JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY 2021年第4期19卷 2150013-2150013页

作者： Brito, Klairton Lima Alexandrino, Alexsandro Oliveira Oliveira, Andre Rodrigues Dias, Ulisses Dias, Zanoni Univ Estadual Campinas Inst Comp 1251 Albert Einstein Ave BR-13083852 Campinas SP Brazil Univ Estadual Campinas Sch Technol 1888 Paschoal Marmo St BR-13484332 Limeira SP Brazil

In the field of comparative genomics, one way of comparing two genomes is through the analysis of how they distinguish themselves based on a set of mutations called rearrangement events. When considering that genomes undergo different types of rearrangements, it can be assumed that some events are more common than others. To model this assumption, one can assign different weights to different events, where common events tend to cost less than others. However, this approach, called weighted, does not guarantee that the rearrangement assumed to be the most frequent will be also the most frequently returned by proposed algorithms. To overcome this issue, we investigate a new problem where we seek the shortest sequence of rearrangement events able to transform one genome into the other, with a restriction regarding the proportion between the events returned. Here, we consider two rearrangement events: reversal, that inverts the order and the orientation of the genes inside a segment of the genome, and transposition, that moves a segment of the genome to another position. We show the complexity of this problem for any desired proportion considering scenarios where the orientation of the genes is known or unknown. We also develop an approximation algorithm with a constant approximation factor for each scenario and, in particular, we describe an improved (asymptotic) approximation algorithm for the case where the gene orientation is known. At last, we present the experimental tests comparing the proposed algorithms with others from the literature for the version of the problem without the proportion restriction.

关键词： Reversal transposition proportion restriction approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：