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

23rd International Computing and Combinatorics Conference (COCOON)

作者： Shenmaier, Vladimir Sobolev Inst Math 4 Koptyug Ave Novosibirsk 630090 Russia

ISBN: (纸本)9783319623887

The problem is, given a set of n vectors in a d-dimensional normed space, find a subset with the largest length of the sum vector. We prove that, in the case of the lp norm, the problem is APX-complete for any p is an element of [1, 2] and is not in APX if p is an element of (2, infinity). In the case of an arbitrary norm, we propose an algorithm which finds an optimal solution in time 0 (n(d-1)(d + logn)), improving previously known algorithms. In particular, the two-dimensional problem can be solved in nearly linear time. We also present an improved algorithm for the cardinality-constrained version of the problem with running time 0 (dn(d+1)). In the two-dimensional case, this version is shown to be solvable in nearly quadratic time. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Vector sum Normed space Matrix norm Complexity exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal Routing with Resource Assignment for Traveling among Farms 10th

Optimal Routing with Resource Assignment for Traveling among...

引用

10th IFAC Symposium on Robust Control Design (ROCOND)

作者： Nemoto, Takuma Niitsuma, Naoki Kamamichi, Norihiro Tokyo Denki Univ Adachi Ku 5 Senju Asahi Cho Tokyo 1208551 Japan

This paper presents an approach to optimal routing with resource assignment for traveling among scattered farm fields. To this end, a road network among farm fields is created, which has data on shortest paths of all pairs of fields and its distances. Two types of multiple traveling salesman problem (mTSP) formulations solved by an exact algorithm are presented to perform optimal routing. The proposed approach is demonstrated through a numerical experiment using data from an agricultural corporation considered in this paper. The results show features of the mTSP formulations and the proposed approach can yield the optimal routes within 2.4 seconds. Hence the proposed approach is feasible for use in actual daily work. Copyright (C) 2022 The Authors.

关键词： Smart agriculture optimization routing multiple traveling salesman problem exact algorithm

来源：评论

学校读者我要写书评

暂无评论

A speedup technique for (l, d)-motif finding algorithms

引用

BMC Research Notes 2011年第1期4卷 1-7页

作者： Rajasekaran, Sanguthevar Dinh, Hieu Department of CSE University of Connecticut Storrs CT 06269 United States

Background: The discovery of patterns in DNA, RNA, and protein sequences has led to the solution of many vital biological problems. For instance, the identification of patterns in nucleic acid sequences has resulted in the determination of open reading frames, identification of promoter elements of genes, identification of intron/exon splicing sites, identification of SH RNAs, location of RNA degradation signals, identification of alternative splicing sites, etc. In protein sequences, patterns have proven to be extremely helpful in domain identification, location of protease cleavage sites, identification of signal peptides, protein interactions, determination of protein degradation elements, identification of protein trafficking elements, etc. Motifs are important patterns that are helpful in finding transcriptional regulatory elements, transcription factor binding sites, functional genomics, drug design, etc. As a result, numerous papers have been written to solve the motif search problem. Results: Three versions of the motif search problem have been proposed in the literature: Simple Motif Search (SMS), (l, d)-motif search (or Planted Motif Search (PMS)), and Edit-distance-based Motif Search (EMS). In this paper we focus on PMS. Two kinds of algorithms can be found in the literature for solving the PMS problem: exact and approximate. An exact algorithm identifies the motifs always and an approximate algorithm may fail to identify some or all of the motifs. The exact version of PMS problem has been shown to be NP-hard. exact algorithms proposed in the literature for PMS take time that is exponential in some of the underlying parameters. In this paper we propose a generic technique that can be used to speedup PMS algorithms. Conclusions: We present a speedup technique that can be used on any PMS algorithm. We have tested our speedup technique on a number of algorithms. These experimental results show that our speedup technique is indeed very effective. The implemen

关键词： Input Sequence exact algorithm Approximate algorithm Suffix Tree Speedup Technique

来源：评论

学校读者我要写书评

暂无评论

MAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS

引用

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2009年第4期1卷 499-517页

作者： Biro, Peter Manlove, David F. Rizzi, Romeo Univ Glasgow Dept Comp Sci Glasgow G12 8QQ Lanark Scotland Univ Udine Dipartimento Matemat & Informat DIMI Udine Italy

Centralized matching programs have been established in several countries to organize kidney exchanges between incompatible patient-donor pairs. At the heart of these programs are algorithms to solve kidney exchange problems, which can be modelled as cycle packing problems in a directed graph, involving cycles of length 2, 3, or even longer. Usually, the goal is to maximize the number of transplants, but sometimes the total benefit is maximized by considering the differences between suitable kidneys. These problems correspond to computing cycle packings of maximum size or maximum weight in directed graphs. Here we prove the APX-completeness of the problem of finding a maximum size exchange involving only 2-cycles and 3-cycles. We also present an approximation algorithm and an exact algorithm for the problem of finding a maximum weight exchange involving cycles of bounded length. The exact algorithm has been used to provide optimal solutions to real kidney exchange problems arising from the National Matching Scheme for Paired Donation run by NHS Blood and Transplant, and we describe practical experience based on this collaboration.

关键词： Directed graph triangle packing APX-completeness approximation algorithm exact algorithm kidney paired donation

来源：评论

学校读者我要写书评

暂无评论

exact and Parameterized algorithms for Edge Dominating Set in 3-Degree Graphs

Exact and Parameterized Algorithms for Edge Dominating Set i...

引用

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

作者： Xiao, Mingyu Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China

ISBN: (纸本)9783642174605

Given a graph G = (V, E), the edge dominating set problem is to find a minimum set M subset of E such that each edge in E - M has at least one common endpoint with an edge in M. The edge dominating set problem is an important graph problem and has been extensively studied. It is well known that the problem is NP-hard, even when the graph is restricted to a planar or bipartite graph with maximum degree 3. In this paper, we show that the edge dominating set problem in graphs with maximum degree 3 can be solved in O*(1.2721(n)) time and polynomial space, where n is the number of vertices in the graph. We also show that there is an O*(2.2306(k))-time polynomial-space algorithm to decide whether a graph with maximum degree 3 has an edge dominating set of size k or not. Above two results improve previously known results on exact and parameterized algorithms for this problem.

关键词： Edge Dominating Set exact algorithm Parameterized algorithm Cubic Graph

来源：评论

学校读者我要写书评

暂无评论

Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line 9th

Covering, Hitting, Piercing and Packing Rectangles Intersect...

引用

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

作者： Mudgal, Apurva Pandit, Supantha Indian Inst Technol Ropar Dept Comp Sci & Engn Nangal Rd Rupnagar 140001 Punjab India

ISBN: (纸本)9783319266268;9783319266251

We consider special cases of set cover, hitting set, piercing set, and independent set problems for axis-parallel squares and axis-parallel rectangles in the plane, where the objects are intersecting an inclined line, or equivalently a diagonal line. We prove that for axis-parallel unit squares the hitting set and set cover problems are NP-complete, whereas the piercing set and independent set problems are in P. For axis-parallel rectangles, we prove that the piercing set problem is NP-complete, which solves an open question from Correa et al. [Discrete & Computational Geometry (2015) [3]]. Further, we give a n(O)(inverted right perpendicular logc inverted left perpendicular + 1) time exact algorithm for the independent set problem with axis-parallel squares, where n is the number of squares and side lengths of the squares vary from 1 to c. We also prove that when the given objects are unit-height rectangles, both the hitting set and set cover problems are NP-complete. For the same set of objects, we prove that the independent set problem can be solved in polynomial time.

关键词： Covering Hitting Piercing Packing Inclined line Diagonal line NP-complete exact algorithm Unit-height Rectangles Squares

来源：评论

学校读者我要写书评

暂无评论

algorithms for Optimising Heterogeneous Cloud Virtual Machine Clusters 8

Algorithms for Optimising Heterogeneous Cloud Virtual Machin...

引用

8th IEEE International Conference on Cloud Computing Technology and Science (CloudCom)

作者： Thai, Long Varghese, Blesson Barker, Adam Univ St Andrews Sch Comp Sci St Andrews Fife Scotland Queens Univ Belfast Sch EEE & Comp Sci Belfast Antrim North Ireland

ISBN: (纸本)9781509014453

It is challenging to execute an application in a heterogeneous cloud cluster, which consists of multiple types of virtual machines with different performance capabilities and prices. This paper aims to mitigate this challenge by proposing a scheduling mechanism to optimise the execution of Bag-of-Task jobs on a heterogeneous cloud cluster. The proposed scheduler considers two approaches to select suitable cloud resources for executing a user application while satisfying pre-defined Service Level Objectives (SLOs) both in terms of execution deadline and minimising monetary cost. Additionally, a mechanism for dynamic re-assignment of jobs during execution is presented to resolve potential violation of SLOs. Experimental studies are performed both in simulation and on a public cloud using real-world applications. The results highlight that our scheduling approaches result in cost saving of up to 31% in comparison to naive approaches that only employ a single type of virtual machine in a homogeneous cluster. Dynamic reassignment completely prevents deadline violation in the best-case and reduces deadline violations by 95% in the worst-case scenario.

关键词： cloud computing cost minimisation deadline dynamic scheduling exact algorithm hybrid alogirithm static scheduling virtual machine cluster

来源：评论

学校读者我要写书评

暂无评论

A Scalable Approach to exact Resource-Constrained Scheduling Based on a Joint SDC and SAT Formulation 18

A Scalable Approach to Exact Resource-Constrained Scheduling...

引用

ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA)

作者： Dai, Steve Liu, Gai Zhang, Zhiru Cornell Univ Sch Elect & Comp Engn Ithaca NY 14850 USA

ISBN: (纸本)9781450356145

Despite increasing adoption of high-level synthesis (HLS) for its design productivity advantage, success in achieving high quality-of-results out-of-the-box is often hindered by the inexactness of the common HLS optimizations. In particular, while scheduling forms the algorithmic core to HLS technology, current scheduling algorithms rely heavily on fundamentally inexact heuristics that make ad hoc local decisions and cannot accurately and globally optimize over a rich set of constraints. To tackle this challenge, we propose a scheduling formulation based on system of integer difference constraints (SDC) and Boolean satisfiability (SAT) to exactly handle a variety of scheduling constraints. We develop a specialized scheduler based on conflict-driven learning and problem-specific knowledge to optimally and efficiently solve the resource-constrained scheduling problem. By leveraging the efficiency of SDC algorithms and scalability of modern SAT solvers, our scheduling technique is able to achieve on average over 100x improvement in runtime over the integer linear programming (ILP) approach while attaining optimal latency. By integrating our scheduling formulation into a state-of-the-art open-source HLS tool, we further demonstrate the applicability of our scheduling technique with a suite of representative benchmarks targeting FPGAs.

关键词： scalability resource-constrained scheduling integer linear programming exact algorithm ilp system of difference constraints scheduling rcs satisfiability problem-specific knowledge efficiency hls sdc sat optimal solution conflict-driven learning high-level synthesis satisfiability modulo theory

来源：评论

学校读者我要写书评

暂无评论

Minimizing makespan of a production batch within concurrent systems:Seru production perspective

引用

Journal of Management Science and Engineering 2022年第1期7卷 1-18页

作者： Yin Gai Yong Yin Jiafu Tang Shiqiang Liu College of Management Science and Engineering Dongbei University of Finance and EconomicsDalian116025China Graduate School of Business Doshisha UniversityKyoto602-8580Japan School of Economics and Management Fuzhou UniversityFuzhou350108China

This paper discusses the makespan minimization of a production batch within a specific concurrent system,seru production system.A seru production system consists of multiple independent serus.A seru is a compact assembly origination in which products are assembled from-the-beginning-to-the-end without *** capability of a seru production system is its responsiveness.A performance measure used to evaluate a seru system’s responsiveness is the makespan of production batches assembled within the seru *** study addresses the makespan minimization problem through an optimal seru loading *** problem is formulated as a min-max integer optimization *** exact dimension-reduction algorithm is developed to obtain the optimal allocation that minimizes the *** show that the solution space increases very *** contrast,our algorithm is efficient with a polynomial computational complexity of,where is the total number of serus in a seru *** verify the usefulness of the developed exact dimension-reduction algorithm,we compare it with a widely practiced greedy algorithm through *** find that our optimal algorithm is robust in most cases and the greedy algorithm is efficient when variability in production efficiencies is *** result can guide us to adopt different algorithms in different business *** the variability in production efficiencies is high,e.g.,new employees and/or new products assembly,the greedy algorithm is *** other cases,our optimal algorithm should be adopted to obtain the minimum *** also extend the method to the application of a rotating seru.

关键词： Assembly Greedy algorithm Dimension reduction exact algorithm Variability Polynomial computational complexity

来源：评论

学校读者我要写书评

暂无评论

Integrated Optimization in Supply- and Demand-Driven Channels in Two-Stage Supply Chains

Integrated Optimization in Supply- and Demand-Driven Channel...

引用

作者： Li, Xin PennState University Libraries

学位级别：Doctor of Philosophy

Essentially, supply chain management (SCM) is the coordination and integration of the flows of materials, information, and finances across the entire supply chain, which encompasses a wide range of important activities in a company’s operation, including supplier management, supply planning, production scheduling, inventory management, etc. Due to the systematic nature of SCM, many of its activities are highly interrelated and should be studied integrally to help the company gain maximum benefit. This dissertation aims at addressing the integrated optimization problems of some critical components in SCM, particularly, for supply- and demand-driven channels in two-stage supply chains. Four specific problems are incorporated in this *** first problem integrates the decision making process of supplier selection and lot sizing for a manufacturer who orders one type of product from multiple candidate suppliers to fulfill a fixed demand rate. Particularly, we consider the case where suppliers are capacitated and offer a certain type of quantity discount. The product’s perfect rate varies among suppliers and a minimum average perfect rate is required. Besides, in order to facilitate production plans, which are usually made on a daily/weekly/monthly basis, each placed orders is required to cover the demand corresponding to an interval that is multiple of a given time unit. A cyclic order schedule is employed, where the entire planning horizon is divided into repeating order cycles and the set of selected suppliers and corresponding order quantities and frequencies are determined accordingly so that the total cost per time unit is minimized. The second problem is similar to the first one but considers a different discount scheme, where the unit price of a product depends on the total order quantity of a given supplier over a certain period of time, instead of a discount applied to an individual order. Two cases are considered: order quantities are continuous/int

关键词： two-stage supply chain integrated optimization mathematical model exact algorithm heuristic supplier selection and lot sizing order acceptance and scheduling source selection and supply planning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：