In the paper we consider the problem of scheduling n identical jobs on 3 uniform machines with speeds s1,s2, and s3 to minimize the schedule length. We assume that jobs are subjected to some kind of ...mutual exclusion constraints, modeled by a cubic incompatibility graph. We show that if the graph is 2-chromatic then the problem can be solved in O(n2) time. If the graph is 3-chromatic, the problem becomes NP-hard even if s1>s2=s3. However, in this case there exists a 10/7-approximation algorithm running in O(n3) time. Moreover, this algorithm solves the problem almost surely to optimality if 3s1/4≤s2=s3.
We revisit the problem of finding a 1-restricted simple 2-matching of maximum cardinality. Recall that, given an undirected graph
G
=
(
V
,
E
)
, a
simple 2-matching
is a subset
M
⊆
E
of edges such ...that each node in
V
is incident to at most two edges in
M
. Clearly, each such
M
decomposes into a node-disjoint collection of paths and circuits.
M
is called
1-restricted
if it contains no isolated edges (i.e. paths of length one). A combinatorial polynomial algorithm for finding such
M
of maximum cardinality and also a min-max relation were devised by Hartvigsen. It was shown that finding such
M
amounts to computing a (not necessarily 1-restricted) simple 2-matching
M
0
of maximum cardinality and subsequently altering it into
M
of the same cardinality so as to minimize the number of isolated edges. While the first phase (which computes
M
0
) runs in
O
E
V
time, the second one (which turns
M
0
into
M
) requires
O
(
V
E
)
time. In this paper we apply the general blocking augmentation approach (initially introduced, e.g., for bipartite matchings by Hopcroft and Karp, and also by Dinic) and present a novel algorithm that reduces the time needed for the second phase to
O
E
V
thus completely closing the gap between 1-restricted and unrestricted cases.
Let k be a fixed integer. We determine the complexity of finding a p-partition (V1,…,Vp) of the vertex set of a given digraph such that the maximum out-degree of each of the digraphs induced by Vi, ...(1≤i≤p) is at least k smaller than the maximum out-degree of D. We show that this problem is polynomial-time solvable when p≥2k and NP-complete otherwise. The result for k=1 and p=2 answers a question posed in 3. We also determine, for all fixed non-negative integers k1,k2,p, the complexity of deciding whether a given digraph of maximum out-degree p has a 2-partition (V1,V2) such that the digraph induced by Vi has maximum out-degree at most ki for i∈2. It follows from this characterization that the problem of deciding whether a digraph has a 2-partition (V1,V2) such that each vertex v∈Vi has at least as many neighbours in the set V3−i as in Vi, for i=1,2 is NP-complete. This solves a problem from 6 on majority colourings.
The studied problem consists in selecting a group of
k
entities out of
n
entities such that their diversity is maximized. Each entity is assumed to be characterized by a single numerical attribute. ...The diversity is measured by the total pairwise Euclidean or squared Euclidean distance. The problem appears in the formation of social or working groups. Under certain conditions, diversity is perceived as a positive factor influencing the group’s effectiveness. We propose simple
O
(
n
+
k
log
k
)
time algorithms to solve this problem for both the total Euclidean and squared Euclidean distances.
Minimal size balanced sets mod p Cuong, Nguyen Phu; Nedev, Zhivko P.; Zungeru, Adamu Murtala
Scientific African,
September 2024, 2024-09-00, 2024-09-01, Volume:
25
Journal Article
Peer reviewed
Open access
A nonempty set S of residues modulo N is said to be balanced if for each x∈S, there is a d with 0<d≤N/2 such that x±dmodN both lie in S. We denote the minimum cardinality of a balanced set modulo N ...by α(N). Minimal size balanced sets are needed for a winning strategy in the Vector game which was introduced together with balanced sets.
In this paper, we describe a polynomial algorithm for constructing a minimal size balanced set modulo p, when p is from two special classes of primes called lucky primes. We prove that lucky primes are all primes among the sequence cn=2n+3+(−1)n3. Then we prove that the numbers cn=2n+3+(−1)n3 are never prime when n is odd and n>1. Thus, the sequence simplifies to cm=2m+13 with m odd. Finally, we prove that if 2p+13 is prime, then p must be a prime.
► This paper proposes a higher-order arc-search polynomial algorithm for convex quadratic programming. ► It shows at the first time that a higher-order method can reach the complexity bound
O
n
log
1
...ϵ
of first-order method. ► It shows that not only the arc-search algorithm has the lowest polynomial bound but also is computationally competitive. ► The preliminary test on standard test problems shows that the algorithm may be competitive to state-of-art software.
Arc-search is developed for linear programming in
24,25. The algorithms search for optimizers along an ellipse that is an approximation of the central path. In this paper, the arc-search method is applied to primal–dual path-following interior-point method for convex quadratic programming. A simple algorithm with iteration complexity
O
n
log
(
1
/
ϵ
)
is devised. Several improvements on the simple algorithm, which improve computational efficiency, increase step length, and further reduce duality gap in every iteration, are then proposed and implemented. It is intuitively clear that the iteration with these improvements will reduce the duality gap more than the iteration of the simple algorithm without the improvements, though it is hard to show how much these improvements reduce the complexity bound. The proposed algorithm is implemented in MATLAB and tested on quadratic programming problems originating from
13. The result is compared to the one obtained by LOQO in
22. The proposed algorithm uses fewer iterations in all these problems and the number of total iterations is 27% fewer than the one obtained by LOQO. This preliminary result shows that the proposed algorithm is promising.
We show that all minimal dominating sets of a chordal bipartite graph can be generated in incremental polynomial, hence output polynomial, time. Enumeration of minimal dominating sets in graphs is ...equivalent to enumeration of minimal transversals in hypergraphs. Whether the minimal transversals of a hypergraph can be enumerated in output polynomial time is a well-studied and challenging question that has been open for several decades. With this result we contribute to the known cases having an affirmative reply to this important question.
In 1965, Jack Edmonds proposed his celebrated polynomial-time algorithm to find a maximum matching in a graph. It is well-known that finding a maximum matching in G is equivalent to finding a maximum ...independent set in the line graph of G. For general graphs, the maximum independent set problem is NP-hard. What makes this problem easy in the class of line graphs and what other restrictions can lead to an efficient solution of the problem? In the present paper, we analyse these and related questions. We also review various techniques that may lead to efficient algorithms for the maximum independent set problem in restricted graph families, with a focus given to augmenting graphs and graph transformations. Both techniques have been used in the solution of Edmonds to the maximum matching problem, i.e. in the solution to the maximum independent set problem in the class of line graphs. We survey various results that exploit these techniques beyond the line graphs.
PDF
