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

A fast combinatorial algorithm for the bilevel knapsack problem with interdiction constraints

MATHEMATICAL PROGRAMMING 2025年第1-2期210卷 847-879页

作者： Weninger, Noah Fukasawa, Ricardo Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and n items. The objective is to select some items to pack into the first knapsack such that the maximum profit attainable from packing some of the remaining items into the second knapsack is minimized. We present a combinatorial branch-and-bound algorithm which outperforms the current state-of-the-art solution method in computational experiments for 99% of the instances reported in the literature. On many of the harder instances, our algorithm is orders of magnitude faster, which enabled it to solve 53 of the 72 previously unsolved instances. Our result relies fundamentally on a new dynamic programming algorithm which computes very strong lower bounds. This dynamic program solves a relaxation of the problem from bilevel to 2n-level where the items are processed in an online fashion. The relaxation is easier to solve but approximates the original problem surprisingly well in practice. We believe that this same technique may be useful for other interdiction problems.

关键词： Bilevel programming Interdiction Knapsack problem combinatorial algorithm Dynamic programming Branch and bound

来源：评论

学校读者我要写书评

暂无评论

combinatorial algorithm FOR CONSTRUCTING A PARAMETRIC FEATURE SPACE FOR THE CLASSIFICATION OF MULTIDIMENSIONAL MODELS

引用

CYBERNETICS AND SYSTEMS ANALYSIS 2014年第4期50卷 627-633页

作者： Knyshov, G. V. Nastenko, Ie. A. Kondrashova, N. V. Nosovets, O. K. Pavlov, V. A. NM Amosov Natl Inst Cardiovasc Surg Kiev Ukraine Natl Tech Univ Ukraine Kyiv Polytechn Inst Kiev Ukraine NAS Int Sci Training Ctr Informat Technol & Syst Kiev Ukraine MES Kiev Ukraine Open Int Univ Human Dev Ukraine Kiev Ukraine

This article considers a combinatorial algorithm for finding the best set of generalized variables to construct a unified structure of models of objects being classified from given data sets on the basis of the principles of the group method of data handling (GMDH). A classifier giving the best representation of characteristics of the objects being classified is proposed to be constructed in the parameter space of the found structure of models.

关键词： classification modeling combinatorial algorithm selection criterion

来源：评论

学校读者我要写书评

暂无评论

A linear-time combinatorial algorithm to find the orthogonal hull of an object on the digital plane

引用

INFORMATION SCIENCES 2012年 216卷 176-195页

作者： Biswas, Arindam Bhowmick, Partha Sarkar, Moumita Bhattacharya, Bhargab B. Bengal Engn & Sci Univ Dept Informat Technol Howrah 711103 India Indian Inst Technol Dept Comp Sci & Engn Kharagpur 721302 W Bengal India Indian Stat Inst Adv Comp & Microelect Unit Kolkata 700108 India

A combinatorial algorithm to compute the orthogonal hull of a digital object imposed on a background grid is presented in this paper. The resolution and complexity of the orthogonal hull can be controlled by varying the grid size, which may be used for a multiresolution analysis of a given object. Existing algorithms on finding the convex hull are based on divide and conquer strategy, sweepline approach, etc., whereas the proposed algorithm is combinatorial in nature whose time complexity is linear on the object perimeter instead of the object area. For a larger grid size, the perimeter of an object decreases in length in terms of grid units, and hence the runtime of the algorithm reduces significantly. The algorithm uses only comparison and addition in the integer domain, thereby making it amenable to usage in real-world applications where speed is a prime factor. Experimental results including the CPU time demonstrate the elegance and efficacy of the proposed algorithm. (C) 2012 Elsevier Inc. All rights reserved.

关键词： combinatorial algorithm Convex hull Digital geometry Image processing Multiresolution analysis Shape analysis

来源：评论

学校读者我要写书评

暂无评论

An improved combinatorial algorithm for Boolean matrix multiplication

引用

INFORMATION AND COMPUTATION 2018年第Part2期261卷 240-247页

作者： Yu, Huacheng Stanford Univ Stanford CA 94305 USA

We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in (O) over cap (n(3)/log(4)n) time, where the Onotation suppresses poly(loglog) factors. This improves the pr... 详细信息

We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in (O) over cap (n(3)/log(4)n) time, where the <^> Onotation suppresses poly(loglog) factors. This improves the previous best combinatorial algorithm by Chan that runs in (O) over cap (n(3)/log(3)n) time. Our algorithm generalizes the divide- and- conquer strategy of Chan's algorithm. Moreover, we propose a general framework for detecting triangles in graphs and computing Boolean matrix multiplication. Roughly speaking, if we can find the "easy parts" of a given instance efficiently, we can solve the whole problem faster than n(3). (C) 2018 Elsevier Inc. All rights reserved.

关键词： Boolean matrix multiplication combinatorial algorithm Recursion

来源：评论

学校读者我要写书评

暂无评论

Identification of a prognostic signature in colorectal cancer using combinatorial algorithm-driven analysis

引用

JOURNAL OF PATHOLOGY CLINICAL RESEARCH 2022年第3期8卷 245-256页

作者： Alnabulsi, Abdo Wang, Tiehui Pang, Wei Ionescu, Marius Craig, Stephanie G. Humphries, Matthew P. McCombe, Kris Tellez, Manuel Salto Alnabulsi, Ayham Murray, Graeme, I Univ Aberdeen Sch Med Med Sci & Nutr Pathol Aberdeen Scotland AiBIOLOGICS Dublin Ireland Univ Aberdeen Sch Biol Sci Aberdeen Scotland Heriot Watt Univ Sch Math & Comp Sci Edinburgh Midlothian Scotland Queens Univ Belfast Patrick G Johnson Ctr Canc Res Precis Med Ctr Belfast Antrim North Ireland Univ Aberdeen Vertebrate Antibodies Ltd Zool Bldg Aberdeen Scotland

Colorectal carcinoma is one of the most common types of malignancy and a leading cause of cancer-related death. Although clinicopathological parameters provide invaluable prognostic information, the accuracy of prognosis can be improved by using molecular biomarker signatures. Using a large dataset of immunohistochemistry-based biomarkers (n = 66), this study has developed an effective methodology for identifying optimal biomarker combinations as a prognostic tool. Biomarkers were screened and assigned to related subsets before being analysed using an iterative algorithm customised for evaluating combinatorial interactions between biomarkers based on their combined statistical power. A signature consisting of six biomarkers was identified as the best combination in terms of prognostic power. The combination of biomarkers (STAT1, UCP1, p-cofilin, LIMK2, FOXP3, and ICOS) was significantly associated with overall survival when computed as a linear variable (chi(2) = 53.183, p < 0.001) and as a cluster variable (chi(2) = 67.625, p < 0.001). This signature was also significantly independent of age, extramural vascular invasion, tumour stage, and lymph node metastasis (Wald = 32.898, p < 0.001). Assessment of the results in an external cohort showed that the signature was significantly associated with prognosis (chi(2) = 14.217, p = 0.007). This study developed and optimised an innovative discovery approach which could be adapted for the discovery of biomarkers and molecular interactions in a range of biological and clinical studies. Furthermore, this study identified a protein signature that can be utilised as an independent prognostic method and for potential therapeutic interventions.

关键词： biomarker colorectal cancer combinatorial analysis combinatorial algorithm immunohistochemistry prognosis tissue microarray

来源：评论

学校读者我要写书评

暂无评论

CA-KSE: a combinatorial algorithm for benchmarking in knowledge sharing environment

引用

International Journal of Intelligent Computing and Cybernetics 2019年第1期12卷 2-22页

作者： Femi Emmanuel Ayo Olusegun Folorunso Sakinat Oluwabukonla Folorunso Department of Computer Science Federal University of AgricultureAbeokutaNigeria Department of Physical and Computer Sciences McPherson UniversitySeriki SotayoNigeria Department of Computer Science College of Physical SciencesFederal University of AgricultureAbeokutaNigeria Department of Mathematical Sciences Olabisi Onabanjo UniversityAgo IwoyeNigeria

Purpose–Over the past decade,the cost of product development has increased drastically,and this is due to the inability of most enterprises to locate suitable and optimal collaborators for knowledge ***,knowledge sharing is a mechanism that helps people find the best collaborators with relevant ***,a new approach for locating optimal collaborators with relevant knowledge is needed,which couldhelp enterprisein reducingcost andtime ina *** aimsto discuss these ***/methodology/approach–One unique challenge in the domain of knowledge sharing is that collaborators do not possess the same number of events resident in the knowledge available for *** this paper,the authors present a new approach for locating optimal collaborators in knowledge-sharing environment using the combinatorial algorithm(CA-KSE).Findings–The proposed pattern-matching approach implemented in Java is considered efficient for solving the issue peculiar to collaboration in knowledge-sharing *** authors benchmarked the proposed approach with its semi-global pairwise alignment and global alignment counterparts through scores comparison and the receiver operating characteristic *** results obtained from the comparisons showedthat CA-KSEis a perfect test havinganarea undercurveof 0.9659,comparedto the other *** limitations/implications–The paper has proposed an efficient algorithm,which is considered better than related methods,for matching several collaborators(more than two)in KS *** method could be deployed in medical field for gene analysis,software organizations for distributed development and academics for knowledge ***/value–One sign of strength of this approach,compared to most sequence alignment approaches that can only match two collaborators at a time,is that it can match several collaborators at a faster rate.

关键词： combinatorial algorithm Knowledge sharing(KS) Collaborators Pattern matching,Benchmark score

来源：评论

学校读者我要写书评

暂无评论

A Fast combinatorial algorithm for the Bilevel Knapsack Problem with Interdiction Constraints 24th

A Fast Combinatorial Algorithm for the Bilevel Knapsack Prob...

引用

24th International Conference on Integer Programming and combinatorial Optimization (IPCO)

作者： Weninger, Noah Fukasawa, Ricardo Univ Waterloo Waterloo ON Canada

ISBN: (纸本)9783031327254;9783031327261

We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and n items. The objective is to select some items to pack into the first knapsack such that the maximum profit attainable from packing some of the remaining items into the second knapsack is minimized. We present a combinatorial branch-and-bound algorithm which outperforms the current state-of-the-art solution method in computational experiments by 4.5 times on average for all instances reported in the literature. On many of the harder instances, our algorithm is hundreds of times faster, and we solved 53 of the 72 previously unsolved instances. Our result relies fundamentally on a new dynamic programming algorithm which computes very strong lower bounds. This dynamic program solves a relaxation of the problem from bilevel to 2n-level where the items are processed in an online fashion. The relaxation is easier to solve but approximates the original problem surprisingly well in practice. We believe that this same technique may be useful for other interdiction problems.

关键词： Bilevel programming Interdiction Knapsack problem combinatorial algorithm Dynamic programming Branch and bound

来源：评论

学校读者我要写书评

暂无评论

An improved combinatorial algorithm for Boolean matrix multiplication 42nd

An improved combinatorial algorithm for Boolean matrix multi...

引用

42nd International Colloquium on Automata, Languages and Programming (ICALP)

作者： Yu, Huacheng Stanford Univ Stanford CA 94305 USA

ISBN: (纸本)9783662476710

关键词： Boolean matrix multiplication combinatorial algorithm Recursion

来源：评论

学校读者我要写书评

暂无评论

Constraining uncertainty of fault orientation using a combinatorial algorithm

引用

COMPUTERS & GEOSCIENCES 2021年 154卷 104777-104777页

作者： Michalak, Michal Pawel Kuzak, Ryszard Gladki, Pawel Kulawik, Agnieszka Ge, Yunfeng Univ Silesia Katowice Fac Nat Sci Inst Earth Sci Bedzinska 60 PL-41205 Sosnowiec Poland AGH Univ Sci & Technol Fac Geol Geophys & Environm Protect Mickiewicza 30 PL-30059 Krakow Poland Univ Silesia Katowice Fac Sci & Technol Inst Math Bankowa 14 PL-40007 Katowice Poland Univ Silesia Katowice Fac Sci & Technol Bankowa 14 PL-40007 Katowice Poland China Univ Geosci Fac Engn 388 Lumo Rd Wuhan Peoples R China

This study presents experimental results from assessing fault orientation using triangulation and a combinatorial algorithm. We constructed two geological surfaces with vertical and inclined faults. These surfaces were documented by boreholes and represented by triangulated surfaces. We first calculated orientations for a small sample of triangles genetically related to faults that were also members of the Delaunay triangulation. To reduce the epistemic uncertainty regarding the true fault strike, we applied a combinatorial algorithm that allowed us to investigate the orientation distribution of all planes genetically related to the fault. The experiment revealed three unintuitive effects that require further studies: 1) greater concentration of observations about the true dip direction;2) the same dip direction for different triangles;and 3) triangles that dip in the opposite direction to the fault. To conduct spatial clustering within surfaces, we suggest considering a broader interval of orientations related to faults. This broader interval serves to honor the observation that orientations can be genetically related to faults, even if they indicate a relatively high directional within-dissimilarity. We suggest statistical methods for circular data to investigate the resulting distributions. The computer code associated with this study is open source and freely available.

关键词： Geological modeling Fault evidence Discontinuity orientation combinatorial algorithm

来源：评论

学校读者我要写书评

暂无评论

A combinatorial approximation algorithm for concurrent flow problem and its application

引用

COMPUTERS & OPERATIONS RESEARCH 2005年第4期32卷 1007-1035页

作者： Chiou, SW Natl Dong Hwa Univ Dept Informat Management Hualien 97401 Taiwan

The multi-commodity flow problem involves simultaneous shipping several different commodities from sources to sinks in a directed network with total amount of flow going through an edge limited by its capacity. The optimization version of the multi-commodity flow problem is the maximum concurrent flow problem, which finds a flow with the minimum congestion. For any positive E, the e-optimal concurrent flow problem is to find a solution whose the congestion value is no more than (1 + epsilon) times the minimum congestion. In recent years, a few fast combinatorial approximation algorithms for the epsilon-optimal concurrent flow problem have been presented. In this paper we propose a new variant of the combinatorial approximation algorithm: CACF with a tighter computation bound in decreasing the values of congestion and the potential function. Numerical comparisons are made between the results obtained by the combinatorial approximation algorithms and those did by the linear programming package CPLEX on large-scale test networks. The application of CACF to efficiently solving the system-optimal network flow problem is given where good results have been obtained. It has shown the capacity of the CACF in dealing with problems of concurrent flow associated. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： concurrent flow problem combinatorial algorithm minimum-cost flow

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：