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

branch and bound algorithms for rate-distortion optimized media streaming

IEEE TRANSACTIONS ON MULTIMEDIA 2006年第1期8卷 170-178页

作者： Röder, M Cardinal, J Hamzaoui, R Univ Konstanz Dept Comp & Informat Sci D-7750 Constance Germany Univ Libre Bruxelles Dept Comp Sci Brussels Belgium

We consider the problem of rate-distortion optimized streaming of packetized multimedia data over a single quality-of-service network using feedback and retransmissions. For a single data unit, we prove that the problem is NP-hard and provide efficient branch and bound algorithms that are much faster than the previously best solution based on dynamic programming. For a group of interdependent data units, we show how to compute optimal solutions with branch and bound algorithms. The branch and bound algorithms for a group of data units are much slower than the current state of the art, a heuristic technique known as sensitivity adaptation. However, in many real-world situations, they provide a significantly better rate-distortion performance.

关键词： branch and bound algorithms computational complexity streaming media

来源：评论

学校读者我要写书评

暂无评论

NK-MaxClique and MMCQ: Tow New Exact branch and bound algorithms for the Maximum Clique Problem

引用

IEEE ACCESS 2020年 8卷 180045-180053页

作者： Mohammadi, Neda Kadivar, Mehdi Shahrekord Univ Dept Comp Sci Shahrekord *** Iran

The maximum clique problem (MCP) is a fundamental problem in combinatorial optimization which finds important applications in real-word. This paper describes two new efficient branch-and-bound maximum clique algorithms NK-MaxClique and MMCQ, designed for solving MCP. We define some pruning conditions based on core numbers and vertex ordering to efficiently remove many of the search space. With respect to this ordering, the algorithms consider the vertices respectively to find the corresponding maximum clique in subproblems. Simulation results demonstrate that the algorithms outperform the previous well-known algorithms for many instances when applied to DIMACS benchmark and random graphs.

关键词： Color Approximation algorithms Heuristic algorithms Upper bound Licenses Optimization Simulation branch and bound algorithms complexity core number maximum clique

来源：评论

学校读者我要写书评

暂无评论

STOCHASTIC MODELING OF branch-AND-bound algorithms WITH BEST-1ST SEARCH

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1985年第9期11卷 922-934页

作者： WAH, BW YU, CF UNIV ILLINOIS COORDINATED SCI LABURBANAIL 61801 PURDUE UNIV SCH ELECT ENGNW LAFAYETTEIN 47907

An approximate stochastic model of branch-and-bound algorithms with a best-first search is proposed. The average memory space required is estimated and the average number of subproblems expanded before the process terminates is predicted. Both of these measures are exponentials of sublinear exponent. In addition, a comparison is made between the number of subproblems expanded in a best-first search and that expanded in a depth-first search. Depth-first search is found to have computational complexity comparable to best-first search when the lower bound function is highly accurate or highly inaccurate; otherwise, the best-fit search is usually preferable. The results derived are useful in examining the efficient evaluation of branch-and-bound algorithms in a virtual memory environment. They also verify that approximations are very effective in lowering the total number of iterations.

关键词： Subproblem Approximations Best First Search branch and bound algorithms Depth First Search Iterations Memory Space

来源：评论

学校读者我要写书评

暂无评论

A branch and bound algorithm for the two-stage assembly scheduling problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1997年第3期103卷 547-556页

作者： Hariri, AMA Potts, CN UNIV SOUTHAMPTON FAC MATH STUDIESSOUTHAMPTON SO17 1BJHANTSENGLAND

This paper develops a branch and bound algorithm for the two-stage assembly scheduling problem. In this problem, there are m machines at the first stage, each of which produces a component of a job. When all pn components are available, a single assembly machine at the second stage completes the job. The objective is to schedule the jobs on the machines so that the maximum completion time, or makespan, is minimized. A lower bound based on solving an artificial two-machine flow shop problem is derived. Also, several dominance theorems are established and incorporated into the branch and bound algorithm. Computational experience with the algorithm is reported for problems with up to 8000 jobs and 10 first-stage machines. (C) 1997 Published by Elsevier Science B.V.

关键词： Completion time jobs Assembly machines machinery machine Myeloma Proteins branch and bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Enhancing branch-and-bound for Multiobjective 0-1 Programming

引用

INFORMS JOURNAL ON COMPUTING 2024年第1期36卷 1-304, C2页

作者： Forget, Nicolas Parragh, Sophie N. Aarhus Univ Sch Business & Social Sci Dept Econ & Business Econ DK-8210 Aarhus 5 Denmark Johannes Kepler Univ Linz Inst Prod & Logist Management A-4040 Linz Austria

In the biobjective branch-and-bound literature, a key ingredient is objective branching, that is, to create smaller and disjoint subproblems in the objective space, obtained from the partial dominance of the lower bound set by the upper bound set. When considering three or more objective functions, however, applying objective branching becomes more complex, and its benefit has so far been unclear. In this paper, we investigate several ingredients that allow us to better exploit objective branching in a multiobjective setting. We extend the idea of probing to multiple objectives for the 0-1 case, enhance it in several ways, and show that, when coupled with objective branching, it results in significant speedups in terms of CPU times. We also show how to adapt it to the general integer case. Furthermore, we investigate cut generation based on the objective branching constraints. Besides, we generalize the best bound idea for node selection to multiple objectives, and we show that the proposed rules outperform, in the multiobjective literature, the commonly employed depth-first and breadth-first strategies. We also analyze problem specific branching rules. We test the proposed ideas on available benchmark instances for three problem classes with three and four objectives, namely, the capacitated facility location problem, the uncapacitated facility location problem, and the knapsack problem. Our enhanced multiobjective branch-and-bound algorithm outperforms the best existing branch-and-bound-based approach and is the first to obtain competitive and even slightly better results than a state-of-the-art objective space search method on a subset of the problem classes.

关键词： multiple criteria integer programming branch and bound algorithms multiobjective combinatorial optimization probing node selection rules

来源：评论

学校读者我要写书评

暂无评论

A branch and bound algorithm for the minimax regret spanning arborescence

引用

JOURNAL OF GLOBAL OPTIMIZATION 2007年第3期37卷 467-480页

作者： Conde, Eduardo Univ Seville Fac Matemat Seville 41012 Spain

The paper considers the problem of finding a spanning arborescence on a directed network whose arc costs are partially known. It is assumed that each arc cost can take on values from a known interval defining a possible economic scenario. In this context, the problem of finding the spanning arborescence which better approaches to that of minimum overall cost under each possible scenario is studied. The minimax regret criterion is proposed in order to obtain such a robust solution of the problem. As it is shown, the bounds on the optimal value of the minimax regret optimization problem obtained in a previous paper, can be used here in a branch and bound algorithm in order to give an optimal solution. The computational behavior of the algorithm is tested through numerical experiments.

关键词： spanning arborescences robust optimization branch and bound algorithms

来源：评论

学校读者我要写书评

暂无评论

A branch, bound, and remember algorithm for the 1|r_i |Σ t _i scheduling problem

引用

JOURNAL OF SCHEDULING 2009年第2期12卷 163-175页

作者： Kao, Gio K. Sewell, Edward C. Jacobson, Sheldon H. Univ Illinois Dept Comp Sci Urbana IL 61801 USA So Illinois Univ Dept Math & Stat Edwardsville IL 62026 USA

This paper presents a modified branch and bound (B&B) algorithm called, the branch, bound, and Remember (BB&R) algorithm, which uses the Distributed Best First Search (DBFS) exploration strategy for solving the 1|r (i) |at (i) scheduling problem, a single machine scheduling problem where the objective is to find a schedule with the minimum total tardiness. Memory-based dominance strategies are incorporated into the BB&R algorithm. In addition, a modified memory-based dynamic programming algorithm is also introduced to efficiently compute lower bounds for the 1 vertical bar r (i) vertical bar at (i) scheduling problem. Computational results are reported, which shows that the BB&R algorithm with the DBFS exploration strategy outperforms the best known algorithms reported in the literature.

关键词： branch and bound algorithms Scheduling theory and algorithms Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

ANALYSIS OF K-NEAREST NEIGHBOR branch AND bound RULES

引用

PATTERN RECOGNITION LETTERS 1986年第2期4卷 71-77页

作者： LARSEN, S KANAL, LN UNIV MARYLAND DEPT COMP SCIMACHINE INTELLIGENCE & PATTERN ANAL LABCOLLEGE PKMD 20742

This paper analyzes the applicability and relative efficiency of four pruning rules for finding k -nearest neighbors by a branch and bound algorithm. Results of experimental simulations with various clustering schemes... 详细信息

关键词： branch and bound algorithms clustering Nearest neighbors

来源：评论

学校读者我要写书评

暂无评论

Parallel branch-and-bound for Two-Stage Stochastic Integer Optimization

Parallel Branch-and-Bound for Two-Stage Stochastic Integer O...

引用

20th International Conference on High Performance Computing (HiPC)

作者： Langer, Akhil Venkataraman, Ramprasad Palekar, Udatta Kale, Laxmikant V. Univ Illinois Dept Comp Sci Urbana IL 61801 USA Univ Illinois Coll Business Urbana IL 61801 USA

ISBN: (纸本)9781479907298

Many real-world planning problems require searching for an optimal solution in the face of uncertain input. One approach to is to express them as a two-stage stochastic optimization problem where the search for an optimum in one stage is informed by the evaluation of multiple possible scenarios in the other stage. If integer solutions are required, then branch-and-bound techniques are the accepted norm. However, there has been little prior work in parallelizing and scaling branch-and-bound algorithms for stochastic optimization problems. In this paper, we explore the parallelization of a two-stage stochastic integer program solved using branch-and-bound. We present a range of factors that influence the parallel design for such problems. Unlike typical, iterative scientific applications, we encounter several interesting characteristics that make it challenging to realize a scalable design. We present two design variations that navigate some of these challenges. Our designs seek to increase the exposed parallelism while delegating sequential linear program solves to existing libraries. We evaluate the scalability of our designs using sample aircraft allocation problems for the US airfleet. It is important that these problems be solved quickly while evaluating large number of scenarios. Our attempts result in strong scaling to hundreds of cores for these datasets. We believe similar results are not common in literature, and that our experiences will feed usefully into further research on this topic.

关键词： Stochastic Integer branch-and-bound techniques optimal solution branch and bound algorithms Face

来源：评论

学校读者我要写书评

暂无评论

Improved branch-and-bound Algorithm for U-Curve Optimization

Improved Branch-and-Bound Algorithm for U-Curve Optimization

引用

IEEE International Workshop on Genomic Signal Processing and Statistics (GENSIPS)

作者： Atashpaz-Gargari, Esmaeil Braga-Neto, Ulisses M. Dougherty, Edward R. Texas A&M Univ Dept Elect & Comp Engn College Stn TX 77843 USA Translat Genom Res Inst Computat Biol Div Phoenix AZ USA

ISBN: (纸本)9781479934621

The U-curve branch-and-bound algorithm for optimization was introduced recently by Ris and collaborators. In this paper we introduce an improved algorithm for finding the optimal set of features based on the U-curve assumption. Synthetic experiments are used to asses the performance of the proposed algorithm, and compare it to exhaustive search and the original algorithm. The results show that the modified U-curve BB algorithm makes fewer evaluations and is more robust than the original algorithm.

关键词： branch and bound algorithms exhaustive search algorithms algorithm optimization Donkeys

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：