Let G be a connected interval graph with n vertices and m edges. For any positive integer k and any subset S of E(G), we design an O(k|S| + m) timealgorithm to find a minimum k-vertex-edge dominating set of G with re...
详细信息
Let G be a connected interval graph with n vertices and m edges. For any positive integer k and any subset S of E(G), we design an O(k|S| + m) timealgorithm to find a minimum k-vertex-edge dominating set of G with respect to S. This shows that the vertex-edge domination problem and the double vertex-edge domination problem can be solved in linear time. Furthermore, the k-vertex-edge domination problem can also be solved in O(km) timealgorithm in interval graphs. Finally, we present a linear timealgorithm to solve the independent vertex-edge domination problem for unit interval graphs.
The triangle packing problem (TPP) is to find the maximum number of pairwise vertex disjoint triangles in a given graph. The TPP is NP-complete in a general graph and even so when a given graph is restricted to a chor...
详细信息
The triangle packing problem (TPP) is to find the maximum number of pairwise vertex disjoint triangles in a given graph. The TPP is NP-complete in a general graph and even so when a given graph is restricted to a chordal graph. On the other hand, the TPP can be solved in polynomialtime for unit interval graphs. For this reason, it is a well-known open problem to prove whether there exists a polynomial time algorithm solving the TPP on interval graphs. In this paper, we give an answer to the problem.(c) 2023 Elsevier B.V. All rights reserved.
In some important application areas of hard real-time systems, e.g., avionics, automotive, industrial controls, and robotics, preemptive sporadic tasks with harmonic periods and constrained deadlines running on a uni-...
详细信息
ISBN:
(纸本)9783031066788;9783031066771
In some important application areas of hard real-time systems, e.g., avionics, automotive, industrial controls, and robotics, preemptive sporadic tasks with harmonic periods and constrained deadlines running on a uni-processor platform play an important role. For such applications we have to check the system task set for guaranteed compliance with deadlines. For this purpose, we present a new algorithm that has a lower computational complexity than known algorithms for the same system class. For this we determine the worst-case response time for each task with a linear computational complexity in the number of tasks, if the task priorities are defined according to their periodic request rates. Otherwise we have to add the time for task ordering.
In pliable index coding, we consider a server with m messages and n clients, where each client has as side information a subset of the messages. We seek to minimize the number of broadcast transmissions, so that each ...
详细信息
In pliable index coding, we consider a server with m messages and n clients, where each client has as side information a subset of the messages. We seek to minimize the number of broadcast transmissions, so that each client can recover any one unknown message she does not already have. Previous work has shown that the pliable index coding problem is NP-hard and requires at most O(log(2)(n)) broadcast transmissions, which indicates exponential savings over the conventional index coding that requires in the worst case O(n) transmissions. In this paper, building on a decoding criterion that we propose, we first design a deterministic polynomial-timealgorithm that can realize the exponential benefits, by achieving, in the worst case, a performance upper bounded by O(log(2)(n)) broadcast transmissions. We extend our algorithm to the t-requests case, where each client requires t unknown messages that she does not have, and show that our algorithm requires at most O(t log(n) + log(2)(n)) broadcast transmissions. We construct lower bound instances that require at least Omega(log(n)) transmissions for linear pliable index coding and at least Omega(t + log(n)) transmissions for the t-requests case, indicating that both our upper and lower bounds are polynomials of log(n) and differ within a factor of O(log(n)). We provide a probabilistic analysis over random instances and show that the required number of transmissions is almost surely Theta(log(n)), as compared with the Theta(n/log(n)) for index coding. In addition, we show that these upper and lower bounds also hold for vector pliable index coding in the worst case instances and the random graph instances, implying that vector coding does not provide benefits in terms of these bounds. Our numerical experiments show that our algorithm outperforms existing algorithms for pliable index coding by up to 50% less transmissions.
This paper discusses the use of polynomial time algorithm for solving the distribution path optimization of unit load automatic distribution system which was used in storage systems commonly,under the condition of spe...
详细信息
This paper discusses the use of polynomial time algorithm for solving the distribution path optimization of unit load automatic distribution system which was used in storage systems commonly,under the condition of specified goods consolidation and rectilinear norm movement mode,establishes the mathematical models according to the characteristics,uses the main circuit which is formed by the algorithm's directed graph as the optimal solution of the model problem,the time complexity of the algorithm is O(n),so it has great practical value.
Aiming at the inefficiency of polynomial time algorithm of linear network coding (NC) for multicast applications, the authors propose an improved algorithm which combines polynomial time algorithm with subtree decompo...
详细信息
Aiming at the inefficiency of polynomial time algorithm of linear network coding (NC) for multicast applications, the authors propose an improved algorithm which combines polynomial time algorithm with subtree decomposition. The algorithm is composed of five steps, including line graph transforming, subtree decomposition, static subtree set generating, assigning of global coding vector, and calculation of local coding vector. Subtree decomposition decreases network scale and coding complexity steeply, so it is an efficient algorithm of linear NC for multicast. An example is given to illustrate the implementation of the algorithm. Detailed analysis to algorithm complexity and a group of numerical experiments are made to show the efficiency of the algorithm.
This paper deals with the single-item capacitated lot sizing problem with concave production and storage costs, considering minimum order quantity and dynamic time windows. The frequency constraints on the production ...
详细信息
This paper deals with the single-item capacitated lot sizing problem with concave production and storage costs, considering minimum order quantity and dynamic time windows. The frequency constraints on the production lots are modeled by dynamic time windows. Between two consecutive production lots, there are at least Q periods and at most R periods. This paper presents an optimal algorithm in 0((T -Q)(2) (R-Q)T-4/Q(3)), which is bounded by O(T-7). (C) 2014 Elsevier B.V. All rights reserved.
Permutations that can be sorted greedily by one or more stacks having various constraints have been studied by a number of authors. A pop-stack is a greedy stack that must empty all entries whenever popped. Permutatio...
详细信息
Permutations that can be sorted greedily by one or more stacks having various constraints have been studied by a number of authors. A pop-stack is a greedy stack that must empty all entries whenever popped. Permutations in the image of the pop-stack operator are said to be pop-stacked. Asinowki, Banderier, Billey, Hackl, and Linusson recently investigated these permutations and calculated their number up to length 16. We give a polynomial-timealgorithm to count pop-stacked permutations up to a fixed length and we use it to compute the first 1000 terms of the corresponding counting sequence. With the 1000 terms, we apply a pair of computational methods to prove some negative results concerning the nature of the generating function for pop-stacked permutations and to empirically predict the asymptotic behavior of the counting sequence using differential approximation.
In this paper we consider the problem of minimizing a general quadratic function over the mixed integer points in an ellipsoid. This problem is strongly NP-hard, NP-hard to approximate within a constant factor, and op...
详细信息
In this paper we consider the problem of minimizing a general quadratic function over the mixed integer points in an ellipsoid. This problem is strongly NP-hard, NP-hard to approximate within a constant factor, and optimal solutions can be irrational. In our main result we show that an arbitrarily good solution can be found in polynomialtime, if we fix the number of integer variables. This algorithm provides a natural extension to the mixed integer setting, of the polynomial solvability of the trust region problem proven by Ye, Karmarkar, Vavasis, and Zippel. As a result, our findings pave the way for designing efficient trust region methods for mixed integer nonlinear optimization problems. The techniques that we introduce are of independent interest and can be used in other mixed integer nonlinear optimization problems. As an example, we consider the problem of minimizing a general quadratic function over the mixed integer points in a polyhedron. For this problem, we show that a solution satisfying weak bounds with respect to optimality can be computed in polynomialtime, provided that the number of integer variables is fixed. It is well known that finding a solution satisfying stronger bounds cannot be done in polynomialtime, unless P = NP.
This paper addresses the minmax regret 1-sink location problem on a dynamic flow path network with parametric weights. A dynamic flow path network consists of an undirected path with positive edge lengths, positive ed...
详细信息
This paper addresses the minmax regret 1-sink location problem on a dynamic flow path network with parametric weights. A dynamic flow path network consists of an undirected path with positive edge lengths, positive edge capacities, and nonnegative vertex weights. A path can be considered as a road, an edge length as the distance along the road, and a vertex weight as the number of people at the site. An edge capacity limits the number of people that can enter the edge per unit time. We consider the problem of locating a sink where all the people evacuate quickly. In our model, each weight is represented by a linear function of a common parameter t, and the decision maker who determines the sink location does not know the value of t. We formulate the problem under such uncertainty as the minmax regret problem. Given t and sink location x, the cost is the sum of arrival times at x for all the people determined by t. The regret for x under t is the gap between this cost and the optimal cost under t. The problem is to find the sink location minimizing the maximum regret over all t. For the problem, we propose an O(n42 alpha(n)alpha(n)2logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>4 2<^>{\alpha (n)} \alpha (n)<^>2 \log n)$$\end{document} timealgorithm, where n is the number of vertices in the network and alpha()\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha (\cdot )$$\end{document} is the inverse Ackermann function. Also, for the special case in which every edge has the same capacity, we show that the complexity can be reduced to O(n32 alpha(n)alpha(n)logn)\documentclass[12pt]{min
暂无评论