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

An approximation algorithm for K-best enumeration of minimal connected edge dominating sets with cardinality constraints

引用

THEORETICAL COMPUTER SCIENCE 2024年 1005卷

作者： Kurita, Kazuhiro Wasa, Kunihiro Nagoya Univ Nagoya Japan Hosei Univ Tokyo Japan

K -best enumeration , which asks to output k -best solutions without duplication, is a helpful tool in data analysis for many fields. In such fields, graphs typically represent data. Thus subgraph enumeration has been paid much attention to such fields. However, k -best enumeration tends to be intractable since, in many cases, finding one optimum solution is NP -hard. To overcome this difficulty, we combine k -best enumeration with a concept of enumeration algorithms called approximation enumeration algorithms . As a main result, we propose a 4 -approximation algorithm for minima l con nected edge dominating sets which outputs k minimal solutions with cardinality at most 4 & sdot;OPT, where OPT is the cardinality of a minimum solution which is not outputted by the algorithm. Our proposed algorithm runs in O(nm 2 Delta) delay, where n, m, Delta are the number of vertices, the number of edges, and the maximum degree of an input graph.

关键词： Output-sensitive enumeration K-best enumeration approximate algorithm Connected edge dominating set

来源：评论

学校读者我要写书评

暂无评论

Bunkering policies for a fuel bunker management problem for liner shipping networks

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2021年第3期289卷 927-939页

作者： De, Arijit Choudhary, Alok Turkay, Metin Tiwari, Manoj K. Newcastle Univ Business Sch Newcastle Upon Tyne NE1 4SE Tyne & Wear England Loughborough Univ Sch Business & Econ Loughborough LE11 3TU Leics England Koc Univ Dept Ind Engn Rumelifeneri Yolu TR-34450 Istanbul Turkey Indian Inst Technol Kharagpur Dept Ind & Syst Engn Kharagpur 721302 W Bengal India

This paper investigates the problem of bunker fuel management for liner shipping networks under different fuel pricing scenarios and taking into consideration different fuel bunkering policies. The fuel consumption of a vessel on a sailing leg may fluctuate as the real vessel speed deviates from the planned vessel speed. Furthermore, fluctuation of fuel prices at various ports increases the complexity of bunkering decisions related to the selection of the bunkering ports and the estimation of bunkered fuel cost. We have developed a mixed integer non-linear programming model to minimize the total expected cost consisting of inventory cost related to container transportation, operating cost associated with ship hiring, as well as bunkering cost and fuel consumption cost at the port. The novelty of our research lies in its consideration of stochastic fuel consumption for different sailing legs, stochastic fuel prices at each port and different fuel bunkering policies to determine optimal bunker fuel management strategies for the selection of bunkering ports and for the estimation of the amount of bunkered fuel required. We have proposed a novel approximate algorithm based on mathematical formulation and the fuel bunkering policies to calculate the total expected cost;the fuel inventory while arriving at and departing from the port;the number of vessels hired for weekly service;the arrival and departure time of the ship;and the amount of fuel bunkered at a port. We have performed extensive computational experiments on the practical routes to demonstrate the applicability, efficacy and robustness of the proposed novel methodology. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Heuristics Liner shipping Bunker fuel management Bunkering policies approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Influential facilities placement over moving objects

引用

DISTRIBUTED AND PARALLEL DATABASES 2021年第3期39卷 607-636页

作者： Zhou, Ying Li, Hui Li, Dan Wang, Meng Cui, Jiangtao Xidian Univ State Key Lab Integrated Serv Networks Xian Peoples R China Xidian Univ Sch Cyber Engn Xian Peoples R China Xian Polytech Univ Sch Comp Sci Xian Peoples R China Xidian Univ Sch Comp Sci & Technol Xian Peoples R China

In this paper we propose and study the problem ofk-Collective influential facility placement over moving object. Specifically, given a set of candidate locations, a group of moving objects, each of which is associated with a collection of reference points, as well as a budgetk, we aim to mine a group ofklocations, the combination of whom can influence the most number of moving objects. We show that this problem is NP-hard and present a basic hill-climb algorithm, namely GreedyP. We prove this method with(1-1/e) approximation ratio. One core challenge is to identify and reduce the overlap of the influence from different selected locations to maximize the marginal benefits. Therefore, the GreedyP approach may be very costly when the number of moving objects is large. In order to address the problem, we also propose another GreedyPS algorithm based on FM-sketch technique, which maps the moving objects to bitmaps such that the marginal benefit can be easily observed through bit-wise operations. Through this way, we are able to save more than a half running time while preserving the result quality. We further present a pair of extensions to the problem, namelyk-Additional andk-Eliminative Influential Facility Placement problems. We also present corresponding approximate solutions towards both extensions and theoretically show that results of both algorithms are guaranteed. Experiments on real datasets verify the efficiency and effectiveness for all these algorithms comparing with baselines.

关键词： Moving objects Location selection Submodular approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

An Approximation algorithm for Unrelated Parallel Machine Scheduling Under TOU Electricity Tariffs

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2021年第2期18卷 743-756页

作者： Pei, Zhi Wan, Mingzhong Jiang, Zhong-Zhong Wang, Ziteng Dai, Xu Zhejiang Univ Technol Coll Mech Engn Hangzhou 310023 Peoples R China Northeastern Univ Sch Business Adm Shenyang 110167 Peoples R China Northeastern Univ Inst Behav & Serv Operat Management Shenyang 110167 Peoples R China Northeastern Univ Key Lab Data Analyt & Optimizat Smart Ind Minist Educ Shenyang 110167 Peoples R China Northern Illinois Univ Dept Ind & Syst Engn De Kalb IL 60115 USA

In an era of sustainable development, considerable emphasis has been put onto energy saving, environment friendly, and social welfare as well as productivity in the manufacturing sector. In this work, an unrelated parallel manufacturing setting with time-of-use (TOU) electricity price is explored, with an aim to reduce the electricity cost and increase productivity simultaneously. A nonlinear mathematical programming model is formulated to exploit the special structure of the scheduling problem, where the quadratic constraints are reformulated as second-order-cone (SOC) constraints, and several tailored cutting planes are introduced to further tighten the feasible region of the problem. Then, the original scheduling problem is transformed into several single-machine scheduling problems with TOU electricity price, which could be relaxed as a single-objective programming problem, and it could be solved rapidly via commercial solvers, such as CPLEX. Based on the optimal solution of the relaxed problem, an approximate algorithm is proposed, where a special rounding technique is employed to assign jobs to the unrelated parallel machines in a local search manner. Furthermore, a lower bound model is constructed by eliminating the nonpreemption constraint, and an iteration-based algorithm is devised to obtain the optimal solution of the lower bound problem. Meanwhile, a dispatch rule-based approach is proposed to provide an upper bound of the scheduling problem with TOU constraint. In the numerical analysis section, the proposed approximate algorithm is validated through extensive testing on various scales of instances, different emphasis on productivity and electricity price, and under two typical TOU electricity pricing policies. It is observed that the gap between the proposed approximate algorithm and CPLEX is mostly within 4%, and the lower/upper bound methods could obtain a relaxed/feasible solution within 0.01 s. Note to Practitioners-Energy saving together with prod

关键词： Job shop scheduling Parallel machines Approximation algorithms Single machine scheduling Pricing Productivity approximate algorithm cutting plane lower bound second-order-cone (SOC) time-of-use (TOU) unrelated parallel machine scheduling

来源：评论

学校读者我要写书评

暂无评论

Event-Participant and Incremental Planning over Event-Based Social Networks

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2021年第2期33卷 474-488页

作者： Cheng, Yurong Yuan, Ye Chen, Lei Giraud-Carrier, Christophe Wang, Guoren Li, Boyang Sch Comp Sci & Technol Beijing Inst Technol Beijing 100811 Peoples R China Northeastern Univ Sch Comp Sci & Engn Qinhuangdao 066004 Hebei Peoples R China Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Peoples R China Brigham Young Univ Dept Comp Sci Provo UT 84602 USA

In recent years, online Event Based Social Network (EBSN) platforms have become increasingly popular. One typical task of EBSN platforms is to help users make suitable and personalized plans for participating in different interesting social events. Existing techniques either ignore the minimum-participant requirement constraint for each event, which is crucially needed for some events to be held successfully, or assume that events would not change once announced. In this paper, we address the above inadequacies of existing EBSN techniques. We formally define the Global Event Planning with Constraints (GEPC) problem, and its incremental variant. Since these problems are NP-hard, and provide approximate solutions. Finally, we verify the effectiveness and efficiency of our proposed algorithms through extensive experiments over real and synthetic datasets.

关键词： Planning event-based social networks incremental planning approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Distributed Fair k-Center Clustering Problems with Outliers 22nd

Distributed Fair k-Center Clustering Problems with Outliers

引用

22nd International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2021)

作者： Yuan, Fan Diao, Luhong Du, Donglei Liu, Lei Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Univ New Brunswick Fac Management Fredericton NB E3B 5A3 Canada

ISBN: (纸本)9783030967727;9783030967710

Big data clustering is a fundamental problem with a vast number of applications. Due to the increasing size of data, interests in clustering problems in distributed computation models have increased. On the other hand, because important decision making is being automated with the help of algorithms, therefore, fairness in algorithms has become an especially important research topic. In this work, we design new distributed algorithms for the fair k-center problem with outliers. Our main contributions are: (1) In the fair k-center problem with outliers setting we give a 4-approximation ratio algorithm. (2) In the distributed fair k-center problem with outliers setting we give a 18-approximation ratio algorithm.

关键词： Clustering problem approximate algorithm Fair k-center problem with outliers Distributed fair k-center problem with outliers

来源：评论

学校读者我要写书评

暂无评论

Maximizing Range Sum in Trajectory Data 38

Maximizing Range Sum in Trajectory Data

引用

38th IEEE International Conference on Data Engineering (ICDE)

作者： Zhang, Kaiqi Gao, Hong Han, Xixian Chen, Jian Li, Jianzhong Harbin Inst Technol Sch Comp Sci Harbin Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Fac Comp Sci & Control Engn Shenzhen Peoples R China

ISBN: (数字)9781665408837

ISBN: (纸本)9781665408837

Maximizing Range Sum (MaxRS) query is a basic operation in computational geometry and database communities. Given a set of weighted objects in 2-dimensional space and a rectangle, MaxRS query aims to find an optimal position of the rectangle to maximize the total weight of covered objects (i.e., Range Sum). All the existing literature for MaxRS query commonly assumes that every object is associated with a unique point. In real applications, however, every object (e.g., GPS-enabled moving vehicle) is related to a trajectory including a sequence of points, which goes beyond this restrictive assumption. How to tackle the problem of MaxRS query in trajectory data (MaxRST) is important and challenging. In this paper, we propose the definition of MaxRST query where a trajectory is covered by a rectangle if at least one of points in the trajectory is enclosed by the rectangle. We propose a novel method to solve MaxRST query by converting it to rectilinear polygon intersection problem. Then, an interval-tree-based partitioning technique is developed to efficiently settle rectilinear polygon intersection problem. To further shorten the response time, we present (epsilon, delta)-approximate MaxRST query, which returns an approximate answer having the relative error epsilon to the optimal covered weight with probability at least delta. Furthermore, two complementary sampling-based (epsilon, delta)-approximate MaxRST algorithms are proposed. One performs random sampling with replacements on rectilinear polygons and the sample size is irrelevant to the number of trajectories. The other employs grid shifting technique to reduce sample size yet requires an extra cost for grid construction. The theoretical analysis and experimental results show that our proposed algorithms have high performance in terms of efficiency and accuracy.

关键词： MaxRS query approximate algorithm Sampling Trajectory data

来源：评论

学校读者我要写书评

暂无评论

Efficient and Provable Effective Resistance Computation on Large Graphs: An Index-based Approach

引用

Proceedings of the ACM on Management of Data 2024年第3期2卷 1-27页

作者： Meihao Liao Junjie Zhou Rong-Hua Li Qiangqiang Dai Hongyang Chen Guoren Wang Beijing Institute of Technology Beijing China Beijing Institude of technology Beijing China Zhejiang Lab Zhejiang China

Effective resistance (ER) is a fundamental metric for measuring node similarities in a graph, and it finds applications in various domains including graph clustering, recommendation systems, link prediction, and graph neural networks. The state-of-the-art algorithm for computing effective resistance relies on a landmark technique, which involves selecting a node that is easy to reach by all the other nodes as a landmark. The performance of this technique heavily depends on the chosen landmark node. However, in many real-life graphs, it is not always possible to find an easily reachable landmark node, which can significantly hinder the algorithm's efficiency. To overcome this problem, we propose a novel multiple landmarks technique which involves selecting a set of landmark nodes Vl such that the other nodes in the graph can easily reach any one of a landmark node in Vl. Specifically, we first propose several new formulas to compute ER with multiple landmarks, utilizing the concept of Schur complement. These new formulas allow us to pre-compute and maintain several small-sized matrices related to Vl as a compact index. With this powerful index technique, we demonstrate that both single-pair and single-source ER queries can be efficiently answered using a newly-developed Vl-absorbed random walk sampling or Vl-absorbed push technique. Comprehensive theoretical analysis shows that all proposed index-based algorithms achieve provable performance guarantees for both single-pair and single-source ER queries. Extensive experiments on 5 real-life datasets demonstrate the high efficiency of our multiple landmarks-based index techniques. For instance, our algorithms, with a 1.5 GB index size, can be up to 4 orders of magnitude faster than the state-of-the-art algorithms while achieving the same accuracy on a large road network.

关键词： approximate algorithm effective resistance graph proximity

来源：评论

学校读者我要写书评

暂无评论

Finding shortest gentle paths on polyhedral terrains by the method of multiple shooting

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2023年 67卷

作者： An, Phan Thanh Le, Nguyen Thi Trang, Le Hong Wong, Raymond Chi-Wing Ho Chi Minh City Univ Technol HCMUT IMACS Inst Math & Computat Sci 268 Ly Thuong Kiet StDist 10 Ho Chi Minh City Vietnam Ho Chi Minh City Univ Technol HCMUT Fac Appl Sci 268 Ly Thuong Kiet StDist 10 Ho Chi Minh City Vietnam Vietnam Natl Univ Ho Chi Minh City Linh Trung Ward Ho Chi Minh City Vietnam Vietnam Acad Sci & Technol VAST Inst Math 18 Hoang Quoc Viet Rd Hanoi Vietnam Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Peoples R China

The problem of finding shortest 0-gentle paths can be stated as follows: given two points p, q on a polyhedral terrain and a slope parameter 0 e (0, n /2), the objective is to find a path joining p and q on the terrain which is shortest such that the slope of the path does not exceed 0. In this paper, we introduce some geometric and analysis properties of such paths and answer the question of whether known results of classical shortest paths hold for shortest 0-gentle paths. An algorithm for approximately computing such shortest 0-gentle paths on terrains is presented, where an approximate shortest 0-gentle path joining two points is a 0-gentle path whose length is the infimum of a sequence of that of 0-gentle paths in which they are decreasing. We also show that the sequence of lengths of paths obtained by the proposed algorithm is convergent. The algorithm is implemented in C++ using CGAL and Open GL in some specific circumstances.

关键词： approximate algorithm Geometric path constraints Method of multiple shooting Motion planning Shortest path Shortest gentle path Straightest geodesic

来源：评论

学校读者我要写书评

暂无评论

Efficient Resistance Distance Computation: The Power of Landmark-based Approaches

引用

Proceedings of the ACM on Management of Data 2023年第1期1卷 1-27页

作者： Meihao Liao Rong-Hua Li Qiangqiang Dai Hongyang Chen Hongchao Qin Guoren Wang Beijing Institute of Technology Beijing China Beijing Institute of Technology Zhejiang China

Resistance distance is a fundamental metric to measure the similarity between two nodes in graphs which has been widely used in many real-world applications. In this paper, we study two problems on approximately computing resistance distance: (i) single-pair query which aims at calculating the resistance distance r(s, t) for a given pair of nodes (s, t); and (ii) single-source query which is to compute all the resistance distances r(s, u) for all nodes u in the graph with a given source node s. Existing algorithms for these two resistance distance query problems are often costly on large graphs. To efficiently solve these problems, we first establish several interesting connections among resistance distance, a new concept called v-absorbed random walk, random spanning forests, and a newly-developed v-absorbed push procedure. Based on such new connections, we propose three novel and efficient sampling-based algorithms as well as a deterministic algorithm for single-pair query; and we develop an online and two index-based approximation algorithms for single-source query. We show that the two index-based algorithms for single-source query take almost the same running time as the algorithms for single-pair query with the aid of a linear-size index. The striking feature of all our algorithms is that they are allowed to select an easy-to-hit node by random walks on the graph. Such an easy-to-hit landmark node v can make the v-absorbed random walk sampling, spanning tree sampling, as well as the v-absorbed push more efficient, thus significantly improving the performance of our algorithms. Extensive experiments on 5 real-life datasets show that our algorithms substantially outperform the state-of-the-art algorithms for two resistance distance query problems in terms of both running time and estimation errors.

关键词： approximate algorithm graph proximity resistance distance

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：