An injective k-coloring of a graph G=(V,E) is a function f:V ->{1,2,& mldr;,k} such that for every pair of vertices u and v having a common neighbor, f(u)not equal f(v). The injective chromatic number chi(i)(G)...
详细信息
An injective k-coloring of a graph G=(V,E) is a function f:V ->{1,2,& mldr;,k} such that for every pair of vertices u and v having a common neighbor, f(u)not equal f(v). The injective chromatic number chi(i)(G) of a graph G is the minimum k for which G admits an injective k-coloring. Given a graph G and a positive integer k, Decide Injective Coloring Problem is to decide whether G admits an injective k-coloring. Decide Injective Coloring Problem is known to be NP-complete for chordal graphs. In this paper, we strengthen this result by proving that Decide Injective coloring Problem remains NP-complete for undirected path graphs, a proper subclass of chordal graphs. Moreover, we show that it is not possible to approximate the injective chromatic number of an undirected path graph within a factor of n1/3-epsilon in polynomialtime for every epsilon>0 unless ZPP = NP. On the positive side, we prove that the injective chromatic number of an interval graph is either Delta(G) or Delta(G)+1, where Delta(G) is the maximum degree of G. We also characterize the interval graphs having chi(i)(G)=Delta(G) and chi(i)(G)=Delta(G)+1. As a consequence of this characterization, we obtain a linear timealgorithm to find the injective chromatic number of an interval graph.
This paper investigates from a theoretical point of view how on-site generation of renewable energy can be incorporated in the optimization of a mid-term production and capacity planning problem. Specifically, we cons...
详细信息
This paper investigates from a theoretical point of view how on-site generation of renewable energy can be incorporated in the optimization of a mid-term production and capacity planning problem. Specifically, we consider the generic case of a manufacturer using two energy sources to supply the electricity demand of its plant: an on-site renewable energy source and the electricity grid. The renewable energy source is considered to be free of use, but its available amount of energy fluctuates over time, whereas the grid power is virtually unlimited but incurs a cost per kWh purchased from the external provider. The objective is to satisfy a time- varying demand at a minimal cost over a mid-term horizon. The plant has a stationary nominal production capacity. To deal with the fluctuation of both the demand and the amount of energy supplied by the on-site source, the production capacity can be temporally increased by installing additional capacity, typically by changing the shift pattern or opening more production lines. Increasing the capacity allows to respond to peak demand and to build stock in periods where the energy is cheap but incurs a fixed cost. We study if an optimal solution of this integrated production, capacity, and energy planning problem can be computed efficiently to provide the best compromise. Our objective is to classify the complexity of the deterministic version of the problem. We establish its NP-hardness under mild assumptions and propose three polynomial time algorithms for special cases, according to the amount of energy provided by the renewable source. These algorithms rely on dominance structural properties which allow us to reduce the problem to well-studied lot-sizing problems with capacity or full batch delivery.
The study of structural graph width parameters like tree-width, clique-width and rankwidth has been ongoing during the last five decades, and their algorithmic use has also been increasing (Cygan et al., 2015). New wi...
详细信息
The study of structural graph width parameters like tree-width, clique-width and rankwidth has been ongoing during the last five decades, and their algorithmic use has also been increasing (Cygan et al., 2015). New width parameters continue to be defined, for example, MIM-width in 2012, twin-width in 2020, and mixed-thinness, a generalization of thinness, in 2022. The concept of thinness of a graph was introduced in 2007 by Mannino, Oriolo, Ricci and Chandran, and it can be seen as a generalization of interval graphs, which are exactly the graphs with thinness equal to one. This concept is interesting because if a representation of a graph as a k-thin graph is given for a constant value k, then several known NP-complete problems can be solved in polynomialtime. Some examples are the maximum weighted independent set problem, solved in the seminal paper by Mannino et al., and the capacitated coloring with fixed number of colors (Bonomo, Mattia and Oriolo, 2011). In this work we present a constructive O(n log(n))-timealgorithm to compute the thinness for any given n-vertex tree, along with a corresponding thin representation. We use intermediate results of this construction to improve known bounds of the thinness of some special families of trees.
We extend congestion games to the setting where players need to make multiple joint choices with interactions in a hierarchical manner (termed joint congestion game). At each choice dimension, players are involved in ...
详细信息
We extend congestion games to the setting where players need to make multiple joint choices with interactions in a hierarchical manner (termed joint congestion game). At each choice dimension, players are involved in a typical congestion game. This game has a feature that the output of one choice dimension serves as an input of another one, and the costs paid by players in different choice dimensions are interdependent. Focusing on the joint congestion game with destination and route choices (i.e., select which destination and which route to complete a trip), we show the existence and uniqueness of the Nash equilibrium under mild assumptions in a nonatomic game setting. Then we investigate the property of the general quantal response equilibrium (QRE) for the joint congestion game in which players have perception errors of their costs (characterized by a probabilistic distribution). The QRE condition for the joint congestion game is further extended to the case where the analyst has only incomplete information about players' perceived costs. A specific cross moment QRE model using the mean and covariance information is accordingly developed to account for both the analyst's and players' imperfect information/perception. We present an equivalent convex program that promises a unique solution for the cross moment QRE model, and provide a polynomialalgorithm to solve it. Numerical results illustrate the features of the developed model for the joint congestion game and demonstrate the efficiency of the solution algorithm on two realistic transportation networks.
Let G = (V, E) be a finite undirected graph. An edge set E ' c E is a dominating induced matching (d.i.m.) in G if every edge in E is intersected by exactly one edge of E '. The Dominating Induced Matching (DI...
详细信息
Let G = (V, E) be a finite undirected graph. An edge set E ' c E is a dominating induced matching (d.i.m.) in G if every edge in E is intersected by exactly one edge of E '. The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in G;this problem is also known as the Efficient Edge Domination problem;it is the Efficient Domination problem for line graphs. The DIM problem is NP -complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but is solvable in polynomialtime for P9 -free graphs [and in linear time for P7 -free graphs] as well as for S1,2,4 -free, for S2,2,2 -free, and for S2,2,3 -free graphs. In this paper, combining two distinct approaches, we solve it in polynomialtime for P10 -free graphs and introduce a partial result for the general case.
We consider two versions of two-machine flow shop scheduling problems, where each job requires an additional resource from the start of its first operation till the end of its second operation. We refer to this resour...
详细信息
We consider two versions of two-machine flow shop scheduling problems, where each job requires an additional resource from the start of its first operation till the end of its second operation. We refer to this resource as storage space. The storage requirement of each job is determined by the processing time of its first operation. The two problems differ from each other in the way resources are allocated for each job. In the first case, the job captures all the necessary units of storage space at the beginning of processing its first operation. In the second case, the job takes up storage space gradually as its first operation is performed. In both problems, the goal is to minimize the makespan. In our paper, we establish the exact borderline between the NP-hard and polynomial-time solvable instances of the problems with respect to the ratio between the storage size and the maximum operation length.
Let G be some simple graph and k be any positive integer. Take h : V ( G )- {0,1, , ... ,k+1} and v is an element of V (G), let AN(h)(v) denote the set of vertices w is an element of N-G (v) with h (w) >= 1. Let AN...
详细信息
Let G be some simple graph and k be any positive integer. Take h : V ( G )- {0,1, , ... ,k+1} and v is an element of V (G), let AN(h)(v) denote the set of vertices w is an element of N-G (v) with h (w) >= 1. Let AN(h)[v] h [v] = AN(h)(v) boolean OR {v}. The function h is a [k]-Roman dominating function of G if h ( AN(h)[v]) >= |AN(h)(v)|+ k holds for any v is an element of V(G). The minimum weight of such a function is called the k-th Roman Domination number of G, which is denoted by gamma(kR) (G). In 2020, Banerjee et al. presented linear timealgorithms to compute the double Roman domination number on proper interval graphs and block graphs. They posed the open question that whether there is some polynomial time algorithm to solve the double Roman domination problem on interval graphs. It is argued that the interval graph is a nontrivial graph class. In this article, we design a simple dynamic polynomial time algorithm to solve the k-th Roman domination problem on interval graphs for each fixed integer k > 1.
The Maximum Weight Independent Set (MWIS) problem on finite undirected graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum weight sum. MWIS is one of the most investigated and most im...
详细信息
The Maximum Weight Independent Set (MWIS) problem on finite undirected graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum weight sum. MWIS is one of the most investigated and most important algorithmic graph problems;it is well known to be NP-complete, and it remains NP-complete even under various strong restrictions such as for triangle-free graphs. Its complexity for P-k-free graphs, k >= 7, is an open problem. In [7], it is shown that MWIS can be solved in polynomialtime for (P-7,triangle)-free graphs. This result is extended by Maffray and Pastor [22] showing that MWIS can be solved in polynomialtime for (P-7,bull)-free graphs. In the same paper, they also showed that MWIS can be solved in polynomialtime for (S-1,S-2,S-3,bull)-free graphs. In this paper, using a similar approach as in [7], we show that MWIS can be solved in polynomialtime for (S-1,S-2,S-4,triangle)-free graphs which generalizes the result for (P-7,triangle)-free graphs. (C) 2021 Elsevier B.V. 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.
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.
暂无评论