•The longest cycle problem on interval graphs is solvable in the first simple polynomial algorithm.•The properties of normal orderings of interval graphs are proposed to solve the longest cycle ...problem.•The longest Hamiltonian connected subgraph problem on interval graphs may be solved by using a similar approach.
The longest cycle problem is the problem of finding a cycle with maximal vertices in a graph. Although it is solvable in polynomial time on few trivial graph classes, the longest cycle problem is well known as NP-complete. A lot of efforts have been devoted to the longest cycle problem. To the best of our knowledge however, there are no polynomial algorithms that can solve any of the non-trivial graph classes. Interval graphs, the intersection of chordal graphs and asteroidal triple-free graphs, are known to be the non-trial graph classes that have polynomial algorithm of the longest cycle problem. In 2009, K. Ioannidou, G.B. Mertzios and S.D. Nikolopoulos presented a polynomial algorithm for the longest path problem on interval graphs in Ioannidou et al. (2009) 19. Inspired by their work, we investigate the longest cycle problem of interval graphs. In this paper, we present the first polynomial algorithm for the longest cycle problem on interval graphs. A dynamic programming approach is proposed in the polynomial algorithm that runs in O(n8) time, where n is the number of vertices of the input graph. Using a similar approach, we design a polynomial algorithm to solve the longest k-thick subgraph problem on interval graphs which will be presented in another separate work. According to the interesting properties of k-thick interval graphs that we discovered (e.g., an interval graph G is traceable if and only if G is 1-thick, G is hamiltonian if and only if G is 2-thick, G is hamiltonian connected if and only if G is 3-thick and so on), the algorithm presented in this paper can be important in studying the spanning connectivity on interval graphs.
highlights•We study single-machine scheduling with an external resource.•We look at four different classes of problems with an external resource.•For each class, we consider four different classical ...objective functions.•We provide a complexity analysis for different members of these four classes.
This paper studies the complexity of single-machine scheduling with an external resource, which is rented for a non-interrupted period. Jobs that need this external resource are executed only when the external resource is available. There is a cost associated with the scheduling of jobs and a cost associated with the duration of the renting period of the external resource. We look at four classes of problems with an external resource: a class of problems where the renting period is budgeted and the scheduling cost needs to be minimized, a class of problems where the scheduling cost is budgeted and the renting period needs to be minimized, a class of two-objective problems where both, the renting period and the scheduling cost, are to be minimized, and a class of problems where a linear combination of the scheduling cost and the renting period is minimized. We provide a thorough complexity analysis (NP-hardness proofs and (pseudo-)polynomial algorithms) for different members of these four classes.
A Polynomial Recognition of Unit Forms Alves, Jesmmer; Castonguay, Diane; Brüstle, Thomas
Electronic notes in discrete mathematics,
November 2016, 2016-11-00, Volume:
55
Journal Article
In this paper we introduce a polynomial algorithm for the recognition of weakly nonnegative unit forms. The algorithm identify hypercritical restrictions testing every 9-point subset of the quadratic ...form associated graph. With Depth First Search strategy, we use a similar approach for the weakly positive recognition.
•A pseudo-polynomial algorithm to solve the two-product capacitated dynamic lot-sizing problem is proposed.•The structure of an optimal solution is analyzed with respect to a type of period called ...regeneration period, which is a period where the inventory of one or both products reach zero.•A master problem network is used to determine the location of regeneration periods.•A subproblem network finds an optimal arrangement of orders between consecutive regeneration periods.•Numerical experiments are performed to show the efficiency of the proposed algorithm.•We show how to extend this approach to any number of products.
In this paper, we analyze a two-product multi-period dynamic lot-sizing problem with a fixed capacity constraint in each period. Each product has a known demand in each period that must be satisfied over a finite planning horizon. The aim of this problem is to minimize the overall cost of placing orders and carrying inventory across all periods. The structure of an optimal solution is analyzed with respect to a type of period called regeneration period, which is a period where the inventory of one or both products reach zero. We show that there is an optimal arrangement of placing orders between consecutive regeneration periods. We propose a pseudo-polynomial algorithm to solve the two-product problem. First, we show how the optimal ordering pattern between two consecutive regeneration periods can be solved using a shortest path problem. Then, we explain how the optimal locations for regeneration periods can be found by solving a shortest path problem on a different network, where each arc corresponds to the shortest path in a subproblem network. We then show how this approach can be scaled up to a three-product problem and generalize this technique to any number of products, as long as it is small.
Identities of the Kauffman monoid Chen, Yuzhu; Hu, Xun; Kitov, Nikita V. ...
Communications in algebra,
05/2020, Volume:
48, Issue:
5
Journal Article
Peer reviewed
We give a transparent combinatorial characterization of the identities satisfied by the Kauffman monoid
Our characterization leads to a polynomial time algorithm to check whether a given identity ...holds in
•We present a polynomial algorithm for user-based relocation and vehicle dispatching.•We solve instances with 100,000 requests and 10,000 vehicles in less than 4 min.•We show that spatial relocation ...outperforms temporal relocation.•We analyze the impact of discount strategies on user comfort.
Free-floating car sharing (FFCS) systems are a promising concept to reduce the traffic volume in cities. However, spatial and temporal mismatches of supply and demand require a relocation of rental cars in order to avoid low degrees of utilization. Here, especially user-based relocation strategies seem to be promising to increase utilization in a cost-efficient manner. However, a thorough optimization-based assessment of user-based relocation strategies for FFCS systems is still missing.
In this paper, we introduce an integer program that optimizes the assignment of user-based relocation strategies in FFCS fleets. We develop a graph representation that allows to reformulate the problem as a k-disjoint shortest paths problem and propose an exact algorithm to solve large-size instances. We show that this algorithm can solve real-world instances within a few milliseconds as well as instances with up to 100,000 customers and 10,000 vehicles in a few minutes.
Furthermore, we present a case study based on real-world data and derive managerial insights on user-based relocation strategies. Our results reveal an upper bound on the benefit of user-based relocation strategies and demonstrate that the employment of such strategies can increase the number of fulfilled rental requests by 21%, while increasing the operator’s revenue by 10%.
•We model a dual-mode production planning problem for manufacturing with two types of emission constraints.•The structure of the model is carefully investigated and some analytical properties are ...proven.•The subproblem of choosing the optimal mix of production modes is addressed.•A polynomial dynamic programming algorithm is developed to solve the problem optimally.
We study a dual-mode production planning problem with emission constraints, where a manufacturer produces a single product with two optional technologies. The manufacturer is equipped with the regular and green technologies to comply with emission limitations, and either one or both can be adopted for production. We first investigate the problem under a mandatory emission-cap policy and then extend it to consider emission trading under an emission cap-and-trade scheme. Based on the structural properties of the problem and a multi-level decomposition approach, a polynomial dynamic programming algorithm is developed to solve the models optimally. Our analysis shows that the manufacturer should only use a mix of both technologies when the emission cap is a binding constraint. Numerical results show that the manufacturer’s decisions and benefits are significantly affected by the emission cap under the mandatory emission-cap policy, especially when the cap is at a relatively low level. However, the carbon price may not remarkably affect the manufacturer’s cost because its influence could be abated through the flexible technology switch under the emission cap-and-trade scheme.
PDF
