Given a digraph D a feedbackarcset is a subset X of the arcs of D such that D - X is acyclic. Let beta(D) denote de minimum cardinality of a feedbackarcset of D. In this paper we prove that a bipartite tournament ...
详细信息
Given a digraph D a feedbackarcset is a subset X of the arcs of D such that D - X is acyclic. Let beta(D) denote de minimum cardinality of a feedbackarcset of D. In this paper we prove that a bipartite tournament T with minimum out-degree at least r satisfies beta(T) >= r(2). A lower bound and an upper bound for beta(T) are given in terms of the bipartite dichromatic number. We define the bipartite dichromatic number of a balanced bipartite tournament T-n,T-n and use this invariant to give an upper bound for the minimum cardinality of a feedbackarcset of T-n,T-n We also prove that for each positive integer k >= 3 there is an integer N(k) such that if n >= N(k), then each balanced bipartite tournament contains an acyclic bipartite tournament T-k(,k).
We consider the (precedence constrained) Minimum feedback arc set problem with triangle inequalities on the weights, which finds important applications in problems of ranking with inconsistent information. We present ...
详细信息
We consider the (precedence constrained) Minimum feedback arc set problem with triangle inequalities on the weights, which finds important applications in problems of ranking with inconsistent information. We present a surprising structural insight showing that the problem is a special case of the minimum vertex cover in hypergraphs with edges of size at most 3.
One of the major challenges in managing 5G networks is the reconfiguration of network slices. The task covers in particular reconfiguration and relocation of virtual network functions (VNFs) so as to match the service...
详细信息
One of the major challenges in managing 5G networks is the reconfiguration of network slices. The task covers in particular reconfiguration and relocation of virtual network functions (VNFs) so as to match the service requirements of the slices and the availability of resources of the data centers. In this article, we study in deep the problem of optimal VNFs reconfiguration analyzing a number of its variants. We define two exact, compact integer linear programming formulations of the VNFs reconfiguration problem, and derive two approximate solution algorithms, one of them based on the column generation method. Numerical tests and comparisons illustrate the performance of the algorithms and the quality of the provided solutions.
We consider the following simple algorithm for feedback arc set problem in weighted tournaments: order the vertices by their weighted indegrees. We show that this algorithm has an approximation guarantee of 5 if the w...
详细信息
We consider the following simple algorithm for feedback arc set problem in weighted tournaments: order the vertices by their weighted indegrees. We show that this algorithm has an approximation guarantee of 5 if the weights satisfy probability constraints ( for any pair of vertices u and v, w(uv) + w(vu) = 1). Special cases of the feedback arc set problem in such weighted tournaments include the feedback arc set problem in unweighted tournaments and rank aggregation. To complement the upper bound, for any constant epsilon > 0, we exhibit an infinite family of ( unweighted) tournaments for which the aforesaid algorithm ( irrespective of how ties are broken) has an approximation ratio of 5 - epsilon.
作者：
Alon, NTel Aviv Univ
Raymond & Beverly Sackler Fac Exact Sci Sch Math & Comp Sci IL-69978 Tel Aviv Israel IAS
Princeton NJ 08540 USA
A tournament is an oriented complete graph. The feedback arc set problem for tournaments is the optimization problem of determining the minimum possible number of edges of a given input tournament T whose reversal mak...
详细信息
A tournament is an oriented complete graph. The feedback arc set problem for tournaments is the optimization problem of determining the minimum possible number of edges of a given input tournament T whose reversal makes T acyclic. Ailon, Charikar, and Newman showed that this problem is NP-hard under randomized reductions. Here we show that it is in fact NP-hard. This settles a conjecture of Bang-Jensen and Thomassen.
The acyclic subgraph problem can be formulated as follows. Given a digraph with arc weights, find a set of arcs containing no directed cycle and having maximum total weight. We investigate this problem from a polyhedr...
详细信息
The acyclic subgraph problem can be formulated as follows. Given a digraph with arc weights, find a set of arcs containing no directed cycle and having maximum total weight. We investigate this problem from a polyhedral point of view and determine several classes of facets for the associated acyclic subgraph polytope. We also show that the separation problem for the facet defining dicycle inequalities can be solved in polynomial time. This implies that the acyclic subgraph problem can be solved in polynomial time for weakly acyclic digraphs. This generalizes a result of Lucchesi for planar digraphs.
暂无评论