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

Equistable simplicial, very well-covered, and line graphs

DISCRETE APPLIED MATHEMATICS 2014年第0期165卷 205-212页

作者： Levit, Vadim E. Milanic, Martin Ariel Univ Samaria Dept Comp Sci & Math IL-40700 Ariel Israel Univ Primorska UP IAM SI-6000 Koper Slovenia Univ Primorska UP FAMNIT SI-6000 Koper Slovenia

We verify the conjectures of Mahadev Peled Sun and of Orlin, both related to equistable graphs, for the classes of simplicial, very well-covered and line graphs. Our results are based on the combinatorial features of triangle graphs and general partition graphs. In particular, we obtain several equivalent characterizations of equistable simplicial graphs, equistable very well-covered graphs, and equistable line graphs, some of which imply polynomial time recognition algorithms for graphs in these classes. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Equistable graph Simplicial graph Very well-covered graph Line graph Strongly equistable graph General partition graph Triangle graph Triangle condition polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

BIPARTITE ANALOGUES OF COMPARABILITY AND COCOMPARABILITY GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2020年第3期34卷 1969-1983页

作者： Hell, Pavol Huang, Jing Lin, Jephian C-H McConnell, Ross M. Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Univ Victoria Dept Math & Stat Victoria BC V8W 3R4 Canada Univ Victoria Dept Math & Stat Victoria BC V8W 2Y2 Canada Colorado State Univ Comp Sci Dept Ft Collins CO 80523 USA

We propose bipartite analogues of comparability and cocomparability graphs. Surprisingly, the two classes coincide. We call these bipartite graphs cocomparability bigraphs. We characterize cocomparability bigraphs in terms of vertex orderings, forbidden substructures, and orientations of their complements. In particular, we prove that cocomparability bigraphs are precisely those bipartite graphs that do not have edge-asteroids;this is analogous to Gallai's structural characterization of cocomparability graphs by the absence of (vertex-) asteroids. Our characterizations imply a robust polynomial-time recognition algorithm for the class of cocomparability bigraphs. Finally, we also discuss a natural relation of cocomparability bigraphs to interval containment bigraphs, resembling a well-known relation of cocomparability graphs to interval graphs.

关键词： cocomparability bigraph chordal bigraph interval bigraph interval containment bigraph two-directional orthogonal-ray graph characterization orientation vertex ordering invertible pair asteroid edge-asteroid recognition polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Parallel machine makespan minimization subject to machine availability and total completion time constraints

引用

JOURNAL OF SCHEDULING 2019年第4期22卷 433-447页

作者： Huo, Yumei CUNY Coll Staten Isl Dept Comp Sci Staten Isl NY 10314 USA

In this paper, we study the parallel machine scheduling subject to machine availability constraint. The jobs can be resumed after being preempted by another job or interrupted by the unavailable intervals. The goal is to minimize the makespan subject to the constraint that the total completion time is minimized. We study two different machine unavailability models. In the first model, each machine has a single unavailable interval which starts from time 0. In the second model, each machine can have multiple unavailable intervals, but at any time, there is at most one machine unavailable. For each model, we show that there is an optimal polynomial time algorithm.

关键词： Bi-criteria scheduling Parallel machines Limited machine availability Total completion time Makespan polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved algorithms for joint optimization of facility locations and network connections

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2016年第3期250卷 745-753页

作者： Lai, Xiaofan Xu, Zhou Hong Kong Polytech Univ Fac Business Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China

This paper studies a k-median Steiner forest problem that jointly optimizes the opening of at most k facility locations and their connections to the client locations, so that each client is connected by a path to an open facility, with the total connection cost minimized. The problem has wide applications in the telecommunication and transportation industries, but is strongly NP-hard. In the literature, only a 2-approximation algorithm is known, it being based on a Lagrangian relaxation of the problem and using a sophisticated primal-dual schema. In this study, we have developed an improved approximation algorithm using a simple transformation from an optimal solution of a minimum spanning tree problem. Compared with the existing 2-approximation algorithm, our new algorithm not only achieves a better approximation ratio that is easier to be proved, but also guarantees to produce solutions of equal or better quality up to 50 percent improvement in some cases. In addition, for two non-trivial special cases, where either every location contains a client, or all the locations are in a tree-shaped network, we have developed, for the first time in the literature, new algorithms that can solve the problem to optimality in polynomial time. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.

关键词： Approximation algorithm polynomial time algorithm Facility location Network connection Steiner forest

来源：评论

学校读者我要写书评

暂无评论

Vehicle scheduling problems with two agents on a line

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第1期45卷 1-18页

作者： Yan, Hao Liu, Peihai Lu, Xiwen East China Univ Sci & Technol Shanghai Peoples R China

This paper studies the two-agent vehicle scheduling problems on a line with the constraint that each job is processed after its release time. All jobs belong to agent A or agent B and each job is located at some vertex on the line. The vehicle starts from an initial vertex vo to process all jobs. The objective of the problem is to find a route of the vehicle so as to minimize the makespan of agent A under the constraint condition that the makespan of agent B is no more than the threshold value Q. This problem can be expressed by the 3-field scheduling notations as line - l vertical bar r(v(j)), C-max(B) <= Q vertical bar C-max(A), For the problem without release time, we show this problem is solvable in polynomial time and an O(n) time algorithm is provided. For the problem with release time, we prove this problem is NP-hard and then, a 3+root 5/2-approximation algorithm is presented. Finally, we conclude the numerical experiments to evaluate the performance of the approximation algorithm.

关键词： Network scheduling Agent scheduling polynomial time algorithm Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A new asymmetric pyramidally solvable class of the traveling salesman problem

引用

OPERATIONS RESEARCH LETTERS 2006年第6期34卷 613-620页

作者： Baki, Mohammed Fazle Univ Windsor Odette Sch Business Windsor ON N9B 3P4 Canada

We present a new method of identifying a class of asymmetric matrices for which an optimal traveling salesman tour exists that is pyramidal. The new class generalizes two previously known classes of matrices and inclu... 详细信息

关键词： traveling salesman problem pyramidal tour polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal Screening of Populations with Heterogeneous Risk Profiles Under the Availability of Multiple Tests

引用

INFORMS JOURNAL ON COMPUTING 2022年第1期34卷 150-164页

作者： Aprahamian, Hrayer El-Amine, Hadi Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77843 USA George Mason Univ Dept Syst Engn & Operat Res Fairfax VA 22030 USA

We study the design of large-scale group testing schemes under a heterogeneous population (i.e., subjects with potentially different risk) and with the availability of multiple tests. The objective is to classify the population as positive or negative for a given binary characteristic (e.g., the presence of an infectious disease) as efficiently and accurately as possible. Our approach examines components often neglected in the literature, such as the dependence of testing cost on the group size and the possibility of no testing, which are especially relevant within a heterogeneous setting. By developing key structural properties of the resulting optimization problem, we are able to reduce it to a network flow problem under a specific, yet not too restrictive, objective function. We then provide results that facilitate the construction of the resulting graph and finally provide a polynomial time algorithm. Our case study, on the screening of HIV in the United States, demonstrates the substantial benefits of the proposed approach over conventional screening methods. Summary of Contribution: This paper studies the problem of testing heterogeneous populations in groups in order to reduce costs and hence allow for the use of more efficient tests for high-risk groups. The resulting problem is a difficult combinatorial optimization problem that is NP-complete under a general objective. Using structural properties specific to our objective function, we show that the problem can be cast as a network flow problem and provide a polynomial time algorithm.

关键词： group testing heterogeneous population multiple tests network flow polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

L1 Norm Minimal Mode-Based Methods for Listing Reaction Network Designs for Metabolite Production

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2021年第5期E104D卷 679-687页

作者： Tamura, Takeyuki Kyoto Univ Bioinformat Ctr Inst Chem Res Uji Kyoto 6110011 Japan

Metabolic networks represent the relationship between chemical reactions and compounds in cells. In useful metabolite production using microorganisms, it is often required to calculate reaction deletion strategies from the original network to result in growth coupling, which means the target metabolite production and cell growth are simultaneously achieved. Although simple elementary flux mode (EFM)-based methods are useful for listing such reaction deletions strategies, the number of cases to be considered is often proportional to the exponential function of the size of the network. Therefore, it is desirable to develop methods of narrowing down the number of reaction deletion strategy candidates. In this study, the author introduces the idea of L1 norm minimal modes to consider metabolic flows whose L1 norms are minimal to satisfy certain criteria on growth and production, and developed a fast metabolic design listing algorithm based on it (minL1-FMDL), which works in polynomial time. Computational experiments were conducted for (1) a relatively small network to compare the performance of minL1-FMDL with that of the simple EFM-based method and (2) a genome-scale network to verify the scalability of minL1-FMDL. In the computational experiments, it was seen that the average value of the target metabolite production rates of minL1-FMDL was higher than that of the simple EFM-based method, and the computation time of minL1-FMDL was fast enough even for genome-scale networks. The developed software, minL1-FMDL, implemented in MATLAB, is available on https://***/(similar to)tamura/software, and can be used for genome-scale metabolic network design for metabolite production.

关键词： metabolic network constraint-based model elementary flux mode linear programming polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Linear regression with partially mismatched data: local search with theoretical guarantees

引用

MATHEMATICAL PROGRAMMING 2023年第2期197卷 1265-1303页

作者： Mazumder, Rahul Wang, Haoyue MIT Cambridge MA 02139 USA

Linear regression is a fundamental modeling tool in statistics and related fields. In this paper, we study an important variant of linear regression in which the predictor-response pairs are partially mismatched. We use an optimization formulation to simultaneously learn the underlying regression coefficients and the permutation corresponding to the mismatches. The combinatorial structure of the problem leads to computational challenges. We propose and study a simple greedy local search algorithm for this optimization problem that enjoys strong theoretical guarantees and appealing computational performance. We prove that under a suitable scaling of the number of mismatched pairs compared to the number of samples and features, and certain assumptions on problem data;our local search algorithm converges to a nearly-optimal solution at a linear rate. In particular, in the noiseless case, our algorithm converges to the global optimal solution with a linear convergence rate. Based on this result, we prove an upper bound for the estimation error of the parameter. We also propose an approximate local search step that allows us to scale our approach to much larger instances. We conduct numerical experiments to gather further insights into our theoretical results, and show promising performance gains compared to existing approaches.

关键词： Linear regression Mismatched data Local search method Permutation learning Mixed integer programming polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Stable sets of maximum weight in (P₇, banner)-free graphs

引用

DISCRETE MATHEMATICS 2008年第1期308卷 20-33页

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

关键词： maximum weight stable set problem (P-7, banner)-free graphs polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：