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

Fast solution of single-machine scheduling problem with embedded jobs

THEORETICAL COMPUTER SCIENCE 2019年第0期782卷 91-106页

作者： Vakhania, Nodari UAEMor Ctr Invest Ciencias Cuernavaca Morelos Mexico

We present a fast polynomial-time algorithm for single-machine scheduling problem with release times (r(j)), processing times (p(j)) and due dates (d(j)) with the objective to minimize the maximum job lateness. The general setting is strongly NP-hard. We expose a particular embedded structure that typically possess a subset of jobs in an instance of the problem. We establish useful properties of the problem instances that tolerate this structure, i.e., in such an instance no subset of embedded jobs overlaps in time with the jobs that do not belong to that subset. Relying on these properties, our algorithm finds an optimal solution for the corresponding class of problem instances. Whether a given problem instance is tolerant of the revealed embedded structure becomes known during the execution of the algorithm. Nevertheless, some sufficient conditions in terms of job parameters can a priori be given. One such a condition is that for any pair of jobs j and i with r(i) > r(j) and d(i) < d(j), d(i) - r(j) - p(j) <= d(i) - r(i) - p(i), and if r(i) + p(i) >= r(j) + p(j), then d(i) >= d(j). As we show, our setting remains powerful enough to model important real-life applications. (C) 2019 Elsevier B.V. All rights reserved.

关键词： polynomial-time algorithm Single-machine scheduling Release time Due date Lateness time complexity

来源：评论

学校读者我要写书评

暂无评论

Load Balancing User Association in Millimeter Wave MIMO Networks

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2019年第6期18卷 2932-2945页

作者： Alizadeh, Alireza Vu, Mai Tufts Univ Dept Elect & Comp Engn Medford MA 02155 USA

User association is necessary in dense millimeter wave (mmWave) networks to determine which base station a user connects to in order to balance base station loads and maximize a network utility. Given that mmWave connections are highly directional and vulnerable to small channel variations, user association changes these connections and hence significantly affects the network interference and consequently the users' instantaneous rates. In this paper, we introduce a new load balancing user association scheme for mmWave MIMO cellular networks which consider these dependencies. We formulate the user association problem as mixed integer nonlinear programming and design a polynomial-time algorithm, called worst connection swapping (WCS), to find a near-optimal solution. Simulation results confirm that the proposed user association scheme improves network performance significantly by adjusting the interference according to the association, and under the max-min fairness, also enhances cell-edge users' transmission rates. We also show how the proposed algorithm can be applied under mobility. Furthermore, the proposed WCS algorithm outperforms other generic algorithms for combinatorial programming such as the genetic algorithm in both accuracy and speed at several orders of magnitude faster, and for small networks, where exhaustive search is possible, it reaches the optimal solution.

关键词： User association mmWave MIMO systems load balancing MINLP polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

On the complexity of the dominating induced matching problem in hereditary classes of graphs

引用

DISCRETE APPLIED MATHEMATICS 2011年第7期159卷 521-531页

作者： Cardoso, Domingos M. Korpelainen, Nicholas Lozin, Vadim V. Univ Warwick DIMAP Coventry CV4 7AL W Midlands England Univ Warwick Math Inst Coventry CV4 7AL W Midlands England Univ Aveiro Dept Matemat P-3810193 Aveiro Portugal

The DOMINATING INDUCED MATCHING problem, also known as EFFICIENT EDGE DOMINATION, is the problem of determining whether a graph has an induced matching that dominates every edge of the graph. This problem is known to be NP-complete. We study the computational complexity of the problem in special graph classes. In the present paper, we identify a critical class for this problem (i.e., a class lying on a "boundary" separating difficult instances of the problem from polynomially solvable ones) and derive a number of polynomial-time results. In particular, we develop polynomial-time algorithms to solve the problem for claw-free graphs and convex graphs. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Dominating induced matching Efficient edge dominating set polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Unique Response Roman Domination: Complexity and algorithms

引用

algorithmICA 2023年第12期85卷 3889-3927页

作者： Banerjee, Sumanta Chaudhary, Juhi Pradhan, Dinabandhu Indian Inst Technol ISM Dept Math & Comp Dhanbad India Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

A function f : V( G) ->{0, 1, 2} is called a Roman dominating function on G = ( V(G), E(G)) if for every vertex v with f (v) = 0, there exists a vertex u epsilon N-G(v) such that f (u) = 2. A function f : V(G). {0, 1, 2} induces an ordered partition ( V-0, V-1, V-2) of V( G), where V-i = {v epsilon V( G) : f (v) = i} for i epsilon{0, 1, 2}. A function f : V(G)->{0, 1, 2} with ordered partition ( V-0, V-1, V-2) is called a unique response Roman function if for every vertex v with f (v) = 0, | N-G(v) boolean AND V-2| <= 1, and for every vertex v with f (v) = 1 or 2, | N-G(v) boolean AND V-2| = 0. A function f : V(G)->{0, 1, 2} is called a unique response Roman dominating function (URRDF) on G if it is a unique response Roman function as well as a Roman dominating function on G. The weight of a unique response Roman dominating function f is the sum f ( V(G)) = Sigma (v epsilon V(G)) f (v), and the minimum weight of a unique response Roman dominating function on G is called the unique response Roman domination number of G and is denoted by u(R)(G). Given a graph G, the Min- URRDF problem asks to find a unique response Roman dominating function of minimum weight on G. In this paper, we study the algorithmic aspects of Min- URRDF. We show that the decision version of Min- URRDF remains NP-complete for chordal graphs and bipartite graphs. We show that for a given graph with n vertices, Min- URRDF cannot be approximated within a ratio of n(1-epsilon) for any epsilon > 0 unless P = NP. We also show that Min- URRDF can be approximated within a factor of Delta + 1 for graphs having maximum degree Delta. On the positive side, we design a linear-time algorithm to solve Min- URRDF for distance-hereditary graphs. Also, we show that Min- URRDF is polynomial-time solvable for interval graphs, and strengthen the result by showing that Min- URRDF can be solved in linear-time for proper interval graphs, a proper subfamily of interval graphs.

关键词： Domination Roman domination Unique response Roman function Unique response Roman domination polynomial-time algorithm NP-completeness

来源：评论

学校读者我要写书评

暂无评论

A study on load-balanced variants of the bin packing problem

引用

DISCRETE APPLIED MATHEMATICS 2019年 264卷 4-14页

作者： Castro-Silva, D. Gourdin, E. Ecole Polytech Palaiseau France Orange Labs Lannion France

We consider several extensions of the fractional bin packing problem, a relaxation of the traditional bin packing problem where the objects may be split across multiple bins. In these extensions, we introduce load-balancing constraints imposing that the share of each object which is assigned to a same bin must be equal. We propose a Mixed-Integer Programming (MIP) formulation and show that the problem becomes NP-hard if we limit to at most 3 the number of bins across which each object can be split. We then consider a variant where the balanced allocations of objects to bins may be done in successive rounds;this problem was inspired by telecommunication applications, and may be used to model simple Live Streaming networks. We show that two rounds are always sufficient to completely assign all objects to the bins and then provide an optimal polynomial-time allocation algorithm for this problem. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Bin packing Load balancing Mixed-integer models polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Independent sets in (P₆, diamond)-free graphs

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2009年第1期11卷 125-140页

作者： Mosca, Raffaele Univ G DAnnunzio Dipartimento Sci I-65127 Pescara Italy

We prove that on the class of (P-6, diamond)-free graphs the Maximum-Weight Independent Set problem and the Minimum-Weight Independent Dominating Set problem can be solved in polynomial time.

关键词： Maximum-Weight Independent Set Minimum-Weight Independent Dominating Set polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

On Polyatomic Tomography over Abelian Groups: Some Remarks on Consistency, Tree Packings and Complexity

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2020年第2期64卷 290-303页

作者： Gritzmann, Peter Langfeld, Barbara Tech Univ Munich Zentrum Math D-85747 Garching Germany Christian Albrechts Univ Kiel Math Seminar D-24118 Kiel Germany

The paper deals with an inverse problem of reconstructing matrices from their marginal sums. More precisely, we are interested in the existence of rxsmatrices for which only the following information is available: The entries belong to known subsets of c distinguishable abelian groups, and the row and column sums of all entries from each group are given. This generalizes Ryser's classical problem of characterizing the set of all 0-1-matrices with given row and column sums and is a basic problem in (polyatomic) discrete tomography. We show that the problem is closely related to packings of trees in bipartite graphs, prove consistency results, give algorithms and determine its complexity. In particular, we find a somewhat unusual complexity behavior: the problem is hard for "small" but easy for "large" matrices.

关键词： Discrete inverse problem Discrete tomography Polyatomic tomography polynomial-time algorithm NP-completeness

来源：评论

学校读者我要写书评

暂无评论

On the complexity of computing mixed volumes

引用

SIAM JOURNAL ON COMPUTING 1998年第2期27卷 356-400页

作者： Dyer, M Gritzmann, P Hufnagel, A Univ Leeds Sch Comp Studies Leeds LS2 9JT W Yorkshire England Tech Univ Munich Ctr Math Sci D-80290 Munich Germany

This paper gives various (positive and negative) results on the complexity of the problem of computing and approximating mixed volumes of polytopes and more general convex bodies in arbitrary dimension. On the negative side, we present several # P-hardness results that focus on the difference of computing mixed volumes versus computing the volume of polytopes. We show that computing the volume of zonotopes is # P-hard (while each corresponding mixed volume can be computed easily) but also give examples showing that computing mixed volumes is hard even when computing the volume is easy. On the positive side, we derive a randomized algorithm for computing the mixed volumes [GRAPHICS] of well-presented convex bodies K(1),...,K(s), where m(1),...,m(s) is an element of N(0) and m(1) greater than or equal to n - psi(n) with psi(n) = o(log n/log log n). The algorithm is an interpolation method based on polynomial-time randomized log algorithms for computing the volume of convex bodies. This paper concludes with applications of our results to various problems in discrete mathematics, combinatorics, computational convexity, algebraic geometry, geometry of numbers, and operations research.

关键词： computational convexity volume mixed volumes convex body polytope zonotope parallelotope computation approximation computational complexity deterministic algorithm randomized algorithm polynomial-time algorithm NP-hardness #P-hardness permanent determinant problems lattice point enumerator partial order Newton polytope polynomial equations

来源：评论

学校读者我要写书评

暂无评论

MARKOV EQUIVALENCE FOR ANCESTRAL GRAPHS

引用

ANNALS OF STATISTICS 2009年第5B期37卷 2808-2837页

作者： Ali, R. Ayesha Richardson, Thomas S. Spirtes, Peter Univ Guelph Dept Math & Stat Guelph ON N1G 2W1 Canada Univ Washington Dept Stat Seattle WA 98195 USA Carnegie Mellon Univ Dept Philosophy Pittsburgh PA 15213 USA

Ancestral graphs can encode conditional independence relations that arise in directed acyclic graph (DAG) models with latent and selection variables. However, for any ancestral graph, there may be several other graphs to which it is Markov equivalent. We state and prove conditions under which two maximal ancestral graphs are Markov equivalent to each other, thereby extending analogous results for DAGs given by other authors. These conditions lead to an algorithm for determining Markov equivalence that runs in time that is polynomial in the number of vertices in the graph.

关键词： Directed acyclic graphs discriminating path inducing path Markov equivalence polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Detecting strong cliques

引用

DISCRETE MATHEMATICS 2019年第9期342卷 2738-2750页

作者： Hujdurovic, Ademir Milanic, Martin Ries, Bernard Univ Primorska UP IAM Muzejski Trg 2 SI-6000 Koper Slovenia Univ Primorska UP FAMNIT Glagoljaska 8 SI-6000 Koper Slovenia Univ Fribourg Dept Informat Bd Perolles 90 CH-1700 Fribourg Switzerland

A strong clique in a graph is a clique intersecting every maximal independent set. We study the computational complexity of six algorithmic decision problems related to strong cliques in graphs and almost completely determine their complexity in the classes of chordal graphs, weakly chordal graphs, line graphs and their complements, and graphs of maximum degree at most three. Our results rely on connections with matchings and relate to several graph properties studied in the literature, including well-covered graphs, localizable graphs, and general partition graphs. (C) 2019 Published by Elsevier B.V.

关键词： Strong clique Weakly chordal graph Line graph Cubic graph NP-hardness polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：