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

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

来源：评论

学校读者我要写书评

暂无评论

DEPTH-M SEARCH IN branch-AND-bound algorithms

引用

INTERNATIONAL JOURNAL OF COMPUTER & INFORMATION SCIENCES 1978年第4期7卷 315-343页

作者： IBARAKI, T Kyoto University

A new search strategy, called depth-msearch, is proposed for branch-and-bound algorithms, wheremis a parameter to be set by the user. In particular, depth-1 search is equivalent to the conventional depth-first search, and depth-∞ search is equivalent to the general heuristic search (including best-bound search as a special case). It is confirmed by computational experiment that the performance of depth-msearch continuously changes from that, of depth-first search to that of heuristic search, whenmis changed from 1 to ∞. The exact upper bound on the size of the required memory space is derived and shown to be bounded byO(nm), wherenis the problem size. Some methods for controllingmduring computation are also proposed and compared, to carry out the entire computation within a given memory space bo

关键词： Searches search strategies heuristic search memory space branches Depth--first search branch and bound algorithms Equivalent

来源：评论

学校读者我要写书评

暂无评论

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 construction of reversible variable length codes

引用

COMPUTER JOURNAL 2004年第6期47卷 701-707页

作者： Tseng, HW Chang, CC Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chaiyi 621 Taiwan

Reversible variable length codes (RVLCs) have been extensively studied. In recent years, many new coding standards such as H.263 MPEG-4 and JPEG-2000 have adopted RVLCs to enhance their error resilient capability. This paper presents a novel algorithm that can construct efficient RVLCs. Distinct from previous Huffman-based schemes, the proposed algorithm employs the branch-and-bound strategy to generate RVLCs. This strategy not only improvesthe coding efficiency but also provides a flexible codeword selection. The experimental results show that the RVLCs obtained by our algorithm outperform all existing RVLCs.

关键词： system recovery code standards codeword JPEG algorithms branch and bound algorithms ALGORITHM CONSTRUCTION RVLC MPEG 4 Standard

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：