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 ...
详细信息
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 polynomialtime recognition algorithms for graphs in these classes. (C) 2013 Elsevier B.V. All rights reserved.
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 ...
详细信息
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.
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...
详细信息
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.
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 o...
详细信息
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 polynomialtime. (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.
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 verte...
详细信息
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 polynomialtime and an O(n) timealgorithm 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.
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 ...
详细信息
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.
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...
详细信息
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 includes some new matrices as well. (c) 2006 Elsevier B.V. All rights reserved.
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 fro...
详细信息
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 polynomialtime. 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.
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 u...
详细信息
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.
We prove that on (P-7, banner)-free graphs the maximum weight stable set problem is solvable in polynomialtime. (c) 2007 Elsevier B.V. All rights reserved.
We prove that on (P-7, banner)-free graphs the maximum weight stable set problem is solvable in polynomialtime. (c) 2007 Elsevier B.V. All rights reserved.
暂无评论