We consider conditional facility location problems with unreliable facilities that can fail with known probabilities. The demand is uniformly distributed over a convex polygon in the rectilinear ...plane where a number of facilities are already present, and it is required to optimally locate another facility. We analyze properties of the exponential family of incremental Voronoi diagrams associated with possible realizations of the set of operational facilities, and, based on this analysis, present polynomial algorithms for three conditional location problems. The approach can be extended to various other conditional location problems with continuous demand and unreliable facilities, under different probabilistic models including ones with correlated facility failures.
A properly colored cycle (path) in an edge-colored graph is a cycle (path) with consecutive edges assigned distinct colors. A monochromatic triangle is a cycle of length 3 with the edges assigned a ...same color. It is known that every edge-colored complete graph without monochromatic triangle always contains a properly colored Hamilton path. In this paper, we investigate the existence of properly colored cycles in edge-colored complete graphs when monochromatic triangles are forbidden. We obtain a vertex-pancyclic analogous result combined with a characterization of all the exceptions. As a consequence, we partially confirm a structural conjecture given by Bollobás and Erdős (1976) and an algorithmic conjecture given by Gutin and Kim (2009).
In the present paper, we give the expression of orthogonal polynomials as Schur complements. We use the Schur complement and its properties to get a recurrence relation between two families of ...orthogonal polynomials. We derive two recursive algorithms for computing the orthogonal polynomials by using the qd algorithm and the well known recurrence relation of Hankel determinants. We also give a useful recurrence relation between the orthogonal polynomials of the same family and auxiliary polynomials, which allows us to build a third algorithm for computing recursively the orthogonal polynomials.
An out‐branching B
u
+ ${B}_{u}^{+}$ (in‐branching B
u
− ${B}_{u}^{-}$) in a digraph D $D$ is a connected spanning subdigraph of D $D$ in which every vertex except the vertex u $u$, called the root, ...has in‐degree (out‐degree) one. It is well known that there exists a polynomial algorithm for deciding whether a given digraph has k $k$ arc‐disjoint out‐branchings with prescribed roots (k $k$ is part of the input). In sharp contrast to this, it is already NP‐complete to decide if a digraph has one out‐branching which is arc‐disjoint from some in‐branching. A digraph is semicomplete if it has no pair of nonadjacent vertices. A tournament is a semicomplete digraph without directed cycles of length 2. In this paper we give a complete classification of semicomplete digraphs that have an out‐branching B
u
+ ${B}_{u}^{+}$ which is arc‐disjoint from some in‐branching B
v
− ${B}_{v}^{-}$ where u
,
v $u,v$ are prescribed vertices of D $D$. Our characterization, which is surprisingly simple, generalizes a complicated characterization for tournaments from 1991 by the first author and our proof implies the existence of a polynomial algorithm for checking whether a given semicomplete digraph has such a pair of branchings for prescribed vertices u
,
v $u,v$ and construct a solution if one exists. This confirms a conjecture of Bang‐Jensen for the case of semicomplete digraphs.
For an integer
t
, we let
P
t
denote the
t
-vertex path. We write
H
+
G
for the disjoint union of two graphs
H
and
G
, and for an integer
r
and a graph
H
, we write
rH
for the disjoint union of
r
...copies of
H
. We say that a graph
G
is
H
-free
if no induced subgraph of
G
is isomorphic to the graph
H
. In this paper, we study the complexity of
k
-coloring, for a fixed integer
k
, when restricted to the class of
H
-free graphs with a fixed graph
H
. We provide a polynomial-time algorithm to test if, for fixed
r
, a
(
P
6
+
r
P
3
)
-free is three-colorable, and find a coloring if one exists. We also solve the list version of this problem, where each vertex is assigned a list of possible colors, which is a subset of
{
1
,
2
,
3
}
. This generalizes results of Broersma, Golovach, Paulusma, and Song, and results of Klimošová, Malik, Masařík, Novotná, Paulusma, and Slívová. Our proof uses a result of Ding, Seymour, and Winkler relating matchings and hitting sets in hypergraphs. We also prove that the problem of deciding if a
(
P
5
+
P
2
)
-free graph has a
k
-coloring is
NP
-hard for every fixed
k
≥
5
.
Corrupted data appears widely in many contemporary applications including voting behavior, high-throughput sequencing and sensor networks. In this article, we consider the sparse modeling via ...L0-regularization under the framework of high-dimensional measurement error models. By utilizing the techniques of the nearest positive semi-definite matrix projection, the resulting regularization problem can be efficiently solved through a polynomial algorithm. Under some interpretable conditions, we prove that the proposed estimator can enjoy comprehensive statistical properties including the model selection consistency and the oracle inequalities. In particular, the nonoptimality of the logarithmic factor of dimensionality will be showed in the oracle inequalities. We demonstrate the effectiveness of the proposed method by simulation studies.
This paper is concerned with algorithms and applications of decreasing minimization on an M-convex set, which is the set of integral elements of an integral base-polyhedron. Based on a recent ...characterization of decreasingly minimal (dec-min) elements, we develop a strongly polynomial algorithm for computing a dec-min element of an M-convex set. The matroidal feature of the set of dec-min elements makes it possible to compute a minimum cost dec-min element, as well. Our second goal is to exhibit various applications in matroid and network optimization, resource allocation, and (hyper)graph orientation. We extend earlier results on semi-matchings to a large degree by developing a structural description of dec-min in-degree bounded orientations of a graph. This characterization gives rise to a strongly polynomial algorithm for finding a minimum edge-cost dec-min orientation.
In this paper, we present an efficient algorithm for minimizing an M♮-convex function under a color-induced budget constraint. The algorithm extends the algorithms by Gabow and Tarjan for finding a ...minimum-weight base of a matroid and by Gottschalk et al. for minimizing a separable discrete convex function on a polymatroid under a color-induced budget constraint. It can also be recognized as an extension of a greedy algorithm for unconstrained M♮-convex function minimization by Murota and Shioura.
Scheduling problems under unavailability constraints has become a popular research topic in the last few years. Despite it's important application in the real world, the uniform parallel machine ...scheduling problem was the least studied due to its complexity. In this paper, we investigated the uniform parallel machine scheduling problem under deterministic availability constraints. Each machine is subject to one unavailability period. Different versions of the problem regarding the type of jobs (identical and non-identical) and the performance measures (the total completion times and the makespan) were studied. For the case of identical jobs and for both performance measures, we developed linear programming models and optimal algorithms to provide a solution to the problem. For the case of non-identical jobs, we proved that the problem is NP-hard and propose a quadratic program. Because, this later cannot solve problems with very large number of jobs and machines, a heuristic was developed to find near optimal solutions to the problem especially with very large number of jobs and machines. The computational results showed that the heuristic's performance is very high regardless the dimensions of problem instances.
PDF
