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

8th International Conference on algorithms and Discrete Applied Mathematics

作者： Moura, Phablo F. S. Ota, Matheus Jun Wakabayashi, Yoshiko Univ Fed Minas Gerais Dept Ciencia Computacao Belo Horizonte MG Brazil Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada Univ Sao Paulo Inst Matemat & Estat Sao Paulo Brazil

ISBN: (纸本)9783030950170;9783030950187

For a given integer k >= 2, partitioning a connected graph into k vertex-disjoint connected subgraphs of similar (or fixed) orders is a classical problem that has been intensively investigated since late seventies. A connected k-partition of a graph is a partition of its vertex set into classes such that each one induces a connected subgraph. Given a connected graph G = (V, E) and a weight function w : V -> Q >=, the balanced connected k-partition problem looks for a connected k-partition of G into classes of roughly the same weight. To model this concept of balance, we seek connected k-partitions that either maximize the weight of a lightest class (MAX-MIN BCPk) or minimize the weight of a heaviest class (MIN-MAX BCPk). These problems, known to be NP-hard, are equivalent only when k/2. We present a simple pseudo-polynomial k/2-approximation algorithm for MIN-MAX BCPk that runs in time O(W vertical bar V vertical bar vertical bar E vertical bar), where W = Sigma(v is an element of V) w(v);then, using a scaling technique, we obtain a (polynomial) (k/2 + epsilon)-approximation with running-time O(vertical bar V vertical bar(3)vertical bar E vertical bar/epsilon), for any fixed epsilon > 0. Additionally, we propose a fixed-parameter tractable algorithm for the unweighted MAX-MIN BCP (where k is part of the input) parameterized by the size of a vertex cover.

关键词： Balanced connected partition approximation algorithm Parameterized algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast Computation of Kemeny's Constant for Directed Graphs 24

Fast Computation of Kemeny's Constant for Directed Graphs

引用

30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

作者： Xia, Haisong Zhang, Zhongzhi Fudan Univ Shanghai Peoples R China

ISBN: (纸本)9798400704901

Kemeny's constant for random walks on a graph is defined as the mean hitting time from one node to another selected randomly according to the stationary distribution. It has found numerous applications and attracted considerable research interest. However, exact computation of Kemeny's constant requires matrix inversion, which scales poorly for large networks with millions of nodes. Existing approximation algorithms either leverage properties exclusive to undirected graphs or involve inefficient simulation, leaving room for further optimization. To address these limitations for directed graphs, we propose two novel approximation algorithms for estimating Kemeny's constant on directed graphs with theoretical error guarantees. Extensive numerical experiments on real-world networks validate the superiority of our algorithms over baseline methods in terms of efficiency and accuracy.

关键词： Random walk approximation algorithm hitting time Kemeny's constant spectral graph theory

来源：评论

学校读者我要写书评

暂无评论

Greedy approximation for the minimum connected dominating set with labeling

引用

OPTIMIZATION LETTERS 2021年第2期15卷 685-700页

作者： Yang, Zishen Shi, Majun Wang, Wei Xi An Jiao Tong Univ Sch Math & Stat 28 Xianning West Rd Xian 710049 Peoples R China

Given a connected graphG=(V,E). A subset C subset of V is adominating setif every vertex ofVis either inCor adjacent to a vertex inC. Further,Cis aconnected dominating setifCis a dominating set and the induced subgraphG[C] is connected. The Minimum Connected Dominating Set (Min-CDS) problem asks to find a connected dominating set with the minimum size, which finds applications in communication networks, in particular, as a virtual backbone in wireless sensor networks. This paper focuses on a variant of the classic Min-CDS problem, called Minimum Connected Dominating Set with Labeling (Min-CDSL), in which we are given a connected graph with vertex labels, and are required to find a connected dominating setCsuch that the number of labels in C(instead of |C|) is minimized. Min-CDSL is apparently a generalization of Min-CDS, and is undoubtedly NP-complete. We give an approximation algorithm for Min-CDSL within performance ratio bounded byln|V(G)|+span(G)+1ln |V(G)|+span(G)+, wherespan(G) refers to the maximumspanof the input labeled graph (i.e., the number of connected components of the induced subgraph by a single label). In general, span(G) is an element of|V(G)| and for a series of labeled graphsspan(G)=O(1) (G)=O(1). For a random graphG is an element of Gn,p ,span(G)=O(ln|V(G)|) (G)=O(\ln |V(G)|) almost surely, and thus our approximation ratio isO(ln|V(G)|) which is reasonable comparing with the best known approximation ratioln|V(G)|+1 for Min-CDS.

关键词： Greedy algorithm Connected dominating set approximation algorithm Performance ratio Labeling

来源：评论

学校读者我要写书评

暂无评论

approximation Schemes for k-Facility Location 28th

Approximation Schemes for k-Facility Location

引用

28th International Computing and Combinatorics Conference (COCOON)

作者： Kong, Xiangyan Zhang, Zhen Cent South Univ Sch Comp Sci & Engn Changsha 410000 Peoples R China Hunan Univ Technol & Business Sch Frontier Crossover Studies Changsha 410000 Peoples R China

ISBN: (纸本)9783031221040;9783031221057

Given a set of clients and a set of facilities associated with non-uniform opening costs, the k-facility location problem is to open no more than k facilities and connect each client to an opened facility, such that the sum of the facility-opening and client-connection costs is minimized. In this paper we give a new sampling-based technique for estimating the locations of the facilities opened in optimal solutions, which yields a (1+ epsilon)-approximation algorithm for the k-facility location problem that runs in O(ndk + (nk(k))(epsilon-O(1))) time in Euclidean metrics.

关键词： approximation algorithm Facility location

来源：评论

学校读者我要写书评

暂无评论

Polynomial-Time approximation Schemes for a Class of Integrated Network Design and Scheduling Problems with Parallel Identical Machines 7th

Polynomial-Time Approximation Schemes for a Class of Integra...

引用

7th International Symposium on Combinatorial Optimization (ISCO)

作者： Saito, Yusuke Shioura, Akiyoshi Tokyo Inst Technol Tokyo 1528550 Japan

ISBN: (纸本)9783031185298;9783031185304

In the integrated network design and scheduling problem (INDS-P), we are asked to repair edges in a graph by using parallel machines so that the performance of the network is recovered by a certain level, and the objective is to minimize the makespan required to finish repairing edges. The main aim of this paper is to show that polynomial-time approximation schemes exist for some class of the problem (INDSP), including the problems associated with minimum spanning tree, shortest path, maximum flow with unit capacity, and maximum-weight matching.

关键词： Network optimization Parallel machine scheduling Polynomial-time approximation scheme approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Cheaper relaxation and better approximation for multi-ball constrained quadratic optimization and extension

引用

JOURNAL OF GLOBAL OPTIMIZATION 2021年第2期80卷 341-356页

作者： Xu, Zhuoyi Xia, Yong Wang, Jiulin Beihang Univ Sch Math Sci LMIB Minist Educ Beijing 100191 Peoples R China

We propose a convex quadratic programming (CQP) relaxation for multi-ball constrained quadratic optimization (MB). (CQP) is shown to be equivalent to semidefinite programming relaxation in the hard case. Based on (CQP), we propose an algorithm for solving (MB), which returns a solution of (MB) with an approximation bound independent of the number of constraints. The approximation algorithm is further extended to solve nonconvex quadratic optimization with more general constraints. As an application, we propose a standard quadratic programming relaxation for finding Chebyshev center of a general convex set with a guaranteed approximation bound.

关键词： Quadratic optimization Semidefinite programming approximation algorithm Chebyshev center

来源：评论

学校读者我要写书评

暂无评论

Enhancing Ride-Pooling Operations: algorithms, Heuristics and Simulation-Based Approaches

Enhancing Ride-Pooling Operations: Algorithms, Heuristics an...

引用

作者： Sundt, Alexander University of Michigan

学位级别：Ph.D., Doctor of Philosophy

The massive growth of ride-hailing and mobility-on-demand (MoD) platforms like Uber, Lyft, and DiDi, as well as advances in connected and automated vehicle (CAV) technology over the past decade have brought promising alternatives to car ownership within reach for many city residents. However, these services come with potentially severe negative effects on cities, such as increasing congestion and emissions due to empty miles. A useful tool to reduce these drawbacks is the introduction and promotion of ride-pooling, which accommodates multiple passenger requests in a single trip. Adopting ride-pooling on a city-wide scale though has significant challenges including customer preferences, computational complexity, and demand uncertainty, all of which affect the benefits of the service. This dissertation aims to examine and address these issues in the context of ride-pooling operations. The success of ride-pooling platforms hinges on whether customer demand will accept it over other alternatives; without enough demand, the system loses the efficiency of multiple customers per vehicle. To this end, we propose a community-based ride-sharing scheme where a system operator recommends travelers with similar travel patterns in order to address concerns about delay and safety while promoting a shared-vehicle environment. By leveraging trajectory data from routing apps, smartphones and CAVs, we can gather information about consumer preferences and construct a mobility profile for them. We modify a traditional Dynamic Time Warping (DTW) algorithm to compare trajectories in users’ profiles and use the resulting measures as a basis for offline recommendation matching. We demonstrate this framework on data from the Microsoft Geolife Dataset. Most ride-pooling platforms operate in a real-time environment, rather than offline, so it is important to consider operational challenges as well. Most notably, solving a matching problem to not only pair riders but also assign groups of reque

关键词： approximation algorithm Simulation Robust optimization Heuristics

来源：评论

学校读者我要写书评

暂无评论

Fast algorithms for maximizing monotone nonsubmodular functions

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第5期43卷 1655-1670页

作者： Liu, Bin Hu, Miaomiao Ocean Univ China Sch Math Sci Qingdao Peoples R China

In recent years, with themore and more researchers studying the problem of maximizing monotone (nonsubmodular) objective functions, the approximation algorithms for this problem have gotten much progress by using some interesting techniques. In this paper, we develop the approximation algorithms for maximizing a monotone function f with generic submodularity ratio gamma subject to certain constraints. Our first result is a simple algorithm that gives a (1 - e(-gamma) - epsilon)-approximation for a cardinality constraint using O(n/epsilon log n/epsilon) queries to the function value oracle. The second result is a new variant of the continuous greedy algorithm for a matroid constraint. We combine the variant of continuous greedy method with the contention resolution schemes to find a solution with approximation ratio (gamma(2)(1 - 1/e)(2) - O(epsilon)), and the algorithm makes O(rn epsilon(-4)log(2) n/epsilon) queries to the function value oracle.

关键词： Nonsubmodular Function Cardinality constraint Matroid constraint approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A primal-dual algorithm for the minimum power partial cover problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第3期44卷 1913-1923页

作者： Li, Menghong Ran, Yingli Zhang, Zhao Zhejiang Normal Univ Coll Math & Comp Sci Jinhua 321004 Zhejiang Peoples R China

In this paper, we study the minimum power partial cover problem (MinPPC). Suppose X is a set of points and S is a set of sensors on the plane, each sensor can adjust its power and the covering range of a sensor s with power p(s) is a disk of radius r(s) satisfying p(s)=c center dot r(s)alpha. Given an integer k <=|X|, the MinPPC problem is to determine the power assignment on every sensor such that at least k points are covered and the total power consumption is the minimum. We present a primal-dual algorithm for MinPPC with approximation ratio at most 3 alpha. This ratio coincides with the best known ratio for the minimum power full cover problem, and improves previous ratio (12+epsilon) for MinPPC which was obtained only for alpha=2.

关键词： Power Partial cover Primal dual approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

The Piggyback Transportation Problem: Transporting drones launched from a flying warehouse

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2022年第2期296卷 504-519页

作者： Wang, Kai Pesch, Erwin Kress, Dominik Fridman, Ilia Boysen, Nils HHL Leipzig Ctr Adv Studies Management Jahnallee 59 D-04109 Leipzig Germany Univ Siegen Management Informat Sci Kohlbettstr 15 D-57068 Siegen Germany Helmut Schmidt Univ Univ Fed Armed Forces Hamburg Business Adm Especially Procurement & Prod Friedrich Ebert Damm 245 D-22159 Hamburg Germany Friedrich Schiller Univ Jena Operat Management Carl Zeiss Str 3 D-07743 Jena Germany

This paper treats the Piggyback Transportation Problem: A large vehicle moves successive batches of small vehicles from a depot to a single launching point. Here, the small vehicles depart toward assigned customers, supply shipments, and return to the depot. Once the large vehicle has returned and another batch of small vehicles has been loaded at the depot, the process repeats until all customers are serviced. With autonomous driving on the verge of practical application, this general setting occurs whenever small autonomous delivery vehicles with limited operating range, e.g., unmanned aerial vehicles (drones) or delivery robots, need to be brought in the proximity of the customers by a larger vehicle, e.g., a truck. We aim at the most elementary decision problem in this context, which is inspired by Amazon's novel last-mile concept, the flying warehouse. According to this concept, drones are launched from a flying warehouse and - after their return to an earthbound depot - are resupplied to the flying warehouse by an air shuttle. We formulate the Piggyback Transportation Problem, investigate its computational complexity, and derive suited solution procedures. From a theoretical perspective, we prove different im portant structural problem properties. From a practical point of view, we explore the impact of the two main cost drivers, the capacity of the large vehicle and the fleet size of small vehicles, on service quality. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Scheduling Logistics Work sharing approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：