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

IEEE International Conference on Information and Automation (ICIA)

作者： Liu, Zhendong Li, Yuejun Zhang, Peng Yang, Zhaohui Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China Shandong Univ Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China

ISBN: (纸本)9781479913343

Determination of Ribonucleic Acid structure is challenging, in order to optimize the RNA pseudoknotted structure, the paper investigates the computational problem and complexity of predicting RNA structure. A new computational method and model with minimum free energy are adopted to predict RNA structure. The main contribution of the paper is to achieves an efficient approximation algorithm for finding RNA pseudoknotted structure and nested structures. We have compared with other algorithms in time complexity and space complexity, the approximation algorithm takes O(n(3)) time and O(n(2)) space, where n is the length of the RNA sequences. The experimental tests for a large database of RNA show that the algorithm is more exact and effective than the algorithms, the algorithm can predict arbitrary pseudoknots, and improve the a predicting accuracy.

关键词： RNA Pseudoknotted structure Minimum free energy Stacking pairs approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Adapative algorithms for crowd-aided categorization

引用

VLDB JOURNAL 2022年第6期31卷 1311-1337页

作者： Li, Yuanbing Wu, Xian Jin, Yifei Li, Jian Li, Guoliang Feng, Jianhua Tsinghua Univ Dept Comp Sci & Technol Beijing Peoples R China Tsinghua Univ Inst Interdisciplinary Informat Sci IIIS Beijing Peoples R China

We study the problem of utilizing human intelligence to categorize a large number of objects. In this problem, given a category hierarchy and a set of objects, we can ask humans to check whether an object belongs to a category, and our goal is to find the most cost-effective strategy to locate the appropriate category in the hierarchy for each object, such that the cost (i.e., the number of questions to ask humans) is minimized. There are many important applications of this problem, including image classification and product categorization. We develop an online framework, in which category distribution is gradually learned and thus an effective order of questions are adaptively determined. We prove that even if the true category distribution is known in advance, the problem is computationally intractable. We develop an approximation algorithm, and prove that it achieves an approximation factor of 2. We also show that there is a fully polynomial time approximation scheme for the problem. Furthermore, we propose an online strategy which achieves nearly the same performance guarantee as the offline optimal strategy, even if there is no knowledge about category distribution beforehand. We develop effective techniques to tolerate crowd errors. Experiments on a real crowdsourcing platform demonstrate the effectiveness of our method.

关键词： Crowdsourcing Human-in-the-loop Categorization Online algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Mechanisms for Resource Allocation and Pricing in Mobile Edge Computing Systems

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2022年第3期33卷 667-682页

作者： Bahreini, Tayebeh Badri, Hossein Grosu, Daniel Wayne State Univ Dept Comp Sci Detroit MI 48202 USA

In this article, we address the resource allocation and monetization challenges in Mobile Edge Computing (MEC) systems, where users have heterogeneous demands and compete for high quality services. We formulate the Edge Resource Allocation Problem (ERAP) as a Mixed-Integer Linear Program (MILP) and prove that ERAP is NP-hard. To solve the problem efficiently, we propose two resource allocation mechanisms. First, we develop an auction-based mechanism and prove that the proposed mechanism is individually-rational and produces envy-free allocations. We also propose an LP-based approximation mechanism that does not guarantee envy-freeness, but it provides solutions that are guaranteed to be within a given distance from the optimal solution. We evaluate the performance of the proposed mechanisms by conducting an extensive experimental analysis on ERAP instances of various sizes. We use the optimal solutions obtained by solving the MILP model using a commercial solver as benchmarks to evaluate the quality of solutions. Our analysis shows that the proposed mechanisms obtain near optimal solutions for fairly large size instances of the problem in a reasonable amount of time.

关键词： Edge computing resource allocation pricing envy-free mechanism approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A 1.5-approximation Route Finding for a Ride-sharing considering Movement of Passengers 1

A 1.5-Approximation Route Finding for a Ride-sharing conside...

引用

1st ACM SIGSPATIAL International Workshop on Sustainable Mobility (SuMob)

作者： Kim, Yonghwan Amano, Masato Yamamoto, Daisuke Nagoya Inst Technol Nagoya Aichi Japan

ISBN: (纸本)9798400703614

MaaS (stands for Mobility as a Service) is a concept that aims to integrate different transportation services into a unified and seamless mobility solution. It encourages a shift away from personally owned modes of transportation, such as private cars, towards a more comprehensive approach that combines public transportation, such as ride-sharing, bike-sharing, carpooling, and other modes of transport into a single and user-centric service. One of the services offered within MaaS is a ride-sharing, which provides several advantages such as cost savings, reduced traffic congestion, or environmental benefits. However, to make a ride-sharing efficient, a sophisticated route finding (i.e., planning) is required to avoid redundantly long routes when picking up or dropping off passengers. In this paper, we consider an efficient ride-sharing route finding for large-vehicles such as buses that starts at the determined location and returns after visiting all the locations, when a set of the locations of the passengers is given. Moreover, we allow passengers to move within a short distance to find more efficient traversal plan. Note that this problem can be reduced to the traveling salesperson problem (with some constraints) which is a well-known NP-hard problem. Hence, we employ a 1.5-approximation algorithm to find an efficient route within a reasonable computational time, moreover, use the Viterbi algorithm to improve the efficiency of the route when allowing each passenger to move.

关键词： ride-sharing route finding approximation algorithm TSP

来源：评论

学校读者我要写书评

暂无评论

Trip-Vehicle Matching and Vehicle Routing Optimization for Ride-Sharing

Trip-Vehicle Matching and Vehicle Routing Optimization for R...

引用

作者： Tian, Ye Iowa State University

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

In recent years, ride-sharing systems have emerged as one of the quintessential examples of sharing economy that can effectively leverage excessive and under-utilized vehicle resources to address many challenges in modern transportation systems (e.g., CO2 emissions, growing fuel prices) and achieve "triple-win'' between the riders, enlisted drivers, and the ride-sharing platform. Lying at the heart of most ride-sharing systems is the problem of joint trip-vehicle matching and routing optimization, which is highly challenging and results in this area remain rather limited. In this thesis, we studied both planning setting and real-time setting for ride-sharing problems. In the planning setting, available drivers and rider demands are given beforehand. We proposed an analytical framework to state the problem and reformulate it as a mixed-integer linear program, which can be solved by global optimization methods. To efficiently solve large-sized problem instances, we developed a memory-augmented time-expansion (MATE) approach which leverages the special problem structure to facilitate approximate (or even exact) algorithm designs. In the real-time setting, rider demands are not available in advance. We proposed a reinforcement learning formulation for ride-sharing that jointly optimizes the rewards and experiences from the perspectives of the drivers and riders, respectively. Then we developed a reactive model-free deep RL approach based on proximal policy optimization (PPO) to solve the joint trip-vehicle matching and routing optimization problem. Finally, we conduct extensive simulations to analyze and verify the performance of our ride-sharing system using real-world datasets. Simulations results show that the proposed framework outperforms a greedy and the receding horizon control (RHC) algorithms under all testing demand patterns.

关键词： approximation algorithm Deep reinforcement learning Ride-sharing Trip-vehicle matching

来源：评论

学校读者我要写书评

暂无评论

Improved Parameterized approximation for Balanced k-Median 15th

Improved Parameterized Approximation for Balanced <i>k</i>-M...

引用

15th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

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

ISBN: (纸本)9783030926816;9783030926809

Balanced k-median is a frequently encountered problem in applications requiring balanced clustering results, which generalizes the standard k-median problem in that the number of clients connected to each facility is constrained by the given lower and upper bounds. This problem is known to be W[2]-hard if parameterized by k, implying that the existence of an FPT(k)-time exact algorithm is unlikely. In this paper, we give a (3 + epsilon)-approximation algorithm for balanced k-median that runs in FPT(k) time, improving upon the previous best approximation ratio of 7.2 + epsilon obtained in the same time. The crucial step in getting the improved ratio and our main technical contribution is a different random sampling method for selecting opened facilities.

关键词： approximation algorithm Parameterized algorithm k-median

来源：评论

学校读者我要写书评

暂无评论

Computational complexity and algorithms for two scheduling problems under linear constraints

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2024年第4期47卷 55-55页

作者： Nip, Kameng Xie, Peng Shenzhen Univ Coll Management Shenzhen Peoples R China Xiamen Univ Sch Math Sci Xiamen Peoples R China

This paper considers two different types of scheduling problems under linear constraints. The first is the single-machine scheduling problem with minimizing total completion time, while the second is the no-wait two-machine flow shop scheduling problem with minimizing makespan. For these two problems, a set of jobs is required to be scheduled to one or two machines. In contrast to the classic scheduling problems, the processing times of jobs are not fixed constants and are not predetermined. The decision-maker only knows that they should satisfy a system of given linear constraints. For both problems, the goal is to determine the processing time for each job and find the schedule that minimizes a particular criterion, namely, the total completion time or the makespan. First, we study the computational complexity and show that both the problems under linear constraints are NP-hard. These hardness results significantly differ from their traditional scheduling counterparts, as both of those are solvable in polynomial time. Then we propose polynomial time exact or approximation algorithms for various special cases. By utilizing the existing scheduling algorithms and the properties of linear programming, we demonstrate that both problems are polynomially solvable when the total number of linear constraints is a fixed constant.

关键词： Scheduling Flow shop Linear programming Computational complexity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

The approximation Ratio of the 2-Opt Heuristic for the Euclidean Traveling Salesman Problem 38

The Approximation Ratio of the 2-Opt Heuristic for the Eucli...

引用

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

作者： Brodowsky, Ulrich A. Hougardy, Stefan Pontsheide 20 D-52076 Aachen Germany Univ Bonn Res Inst Discrete Math Bonn Germany

ISBN: (纸本)9783959771801

The 2-Opt heuristic is a simple improvement heuristic for the Traveling Salesman Problem. It starts with an arbitrary tour and then repeatedly replaces two edges of the tour by two other edges, as long as this yields a shorter tour. We will prove that for Euclidean Traveling Salesman Problems with n cities the approximation ratio of the 2-Opt heuristic is Theta(log n/ log log n). This improves the upper bound of O(log n) given by Chandra, Karloff, and Tovey [3] in 1999.

关键词： traveling salesman problem metric TSP Euclidean TSP 2-Opt approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Utility Aware Offloading for Mobile-Edge Computing

引用

Tsinghua Science and Technology 2021年第2期26卷 239-250页

作者： Ran Bi Qian Liu Jiankang Ren Guozhen Tan School of Computer Science and Technology Dalian University of TechnologyDalian 116024China

Mobile-edge computing casts the computation-intensive and delay-sensitive applications of mobile devices onto network *** offloading incurs extra communication latency and energy cost,and extensive efforts have focused on offloading *** metrics of the system utility are defined to achieve satisfactory quality of ***,most existing works overlook the balance between throughput and *** study investigates the problem of finding an optimal offloading scheme in which the objective of optimization aims to maximize the system utility for leveraging between throughput and *** on Karush-Kuhn-Tucker condition,the expectation of time complexity is analyzed to derive the optimal scheme.A gradient-based approach for utility-aware task offloading is ***,we provide an increment-based greedy approximation algorithm with 1+1/(e-1)*** results show that the proposed algorithms can achieve effective performance in utility and accuracy.

关键词： utility approximation algorithm quality of experience mobile edge computing

来源：评论

学校读者我要写书评

暂无评论

Constrained flows in networks

引用

THEORETICAL COMPUTER SCIENCE 2024年 1010卷

作者： Bang-Jensen, J. Bessy, S. Picasarri-Arrieta, L. Univ Southern Denmark Dept Math & Comp Sci Odense Denmark Univ Montpellier LIRMM CNRS Montpellier France Univ Cote Azur CNRS I3S Inria Sophia Antipolis France

The support of a flow x in a network is the subdigraph induced by the arcs uv for which x(uv) > 0. We discuss a number of results on flows in networks where we put certain restrictions on structure of the support of the flow. Many of these problems are NP-hard because they generalize linkage problems for digraphs. For example deciding whether a network N = (D. s, t, c) has a maximum flow x such that the maximum out-degree of the support D-x of x is at most 2 is NP-complete as it contains the 2-linkage problem as a very special case. Another problem which is NP-complete for the same reason is that of computing the maximum flow we can send from s to t along p paths (called a maximum p-path-flow) in N. Baier et al. (2005) gave a polynomial time algorithm which finds a-path-flow x whose value is at least 2/3 of the value of a optimum p-path-flow when p is an element of{2, 3}, and at least 1/2 when p >= 4. When p = 2, they show that this is best possible unless P=NP. We show for each p >= 2 that the value of a maximum p-path-flow cannot be approximated by any ratio larger than 9/11, unless P=NP. We also consider a variant of the problem where the p paths must be disjoint. For this problem, we give an algorithm which gets within a factor 1/H(p) of the optimum solution, where H(p) is the p'th harmonic number (H(p) similar to ln(p)). We show that in the case where the network is acyclic, we can find such a maximum p-path-flow in polynomial time for every p. We determine the complexity of a number of related problems concerning the structure of flows. For the special case of acyclic digraphs, some of the results we obtain are in some sense best possible.

关键词： Flows (Arc-)disjoint paths with prescribed end vertices Acyclic digraph Polynomial time algorithm NP-complete problem approximation algorithm Parameterised complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：