排序方式: 共有5条查询结果,搜索用时 296 毫秒
1
1.
2.
Social Indicators Research - The importance and centrality of the construct of agency is wellknown amongst social scientists. Yet, there is still little agreement on how this construct should be... 相似文献
3.
Jean Cardinal Samuel Fiorini Gwenaël Joret 《Journal of Combinatorial Optimization》2008,16(4):361-377
We study an information-theoretic variant of the graph coloring problem in which the objective function to minimize is the
entropy of the coloring. The minimum entropy of a coloring is called the chromatic entropy and was shown by Alon and Orlitsky
(IEEE Trans. Inform. Theory 42(5):1329–1339, 1996) to play a fundamental role in the problem of coding with side information. In this paper, we consider the minimum entropy
coloring problem from a computational point of view. We first prove that this problem is NP-hard on interval graphs. We then
show that, for every constant ε>0, it is NP-hard to find a coloring whose entropy is within (1−ε)log n of the chromatic entropy, where n is the number of vertices of the graph. A simple polynomial case is also identified. It is known that graph entropy is a
lower bound for the chromatic entropy. We prove that this bound can be arbitrarily bad, even for chordal graphs. Finally,
we consider the minimum number of colors required to achieve minimum entropy and prove a Brooks-type theorem.
S. Fiorini acknowledges the support from the Fonds National de la Recherche Scientifique and GERAD-HEC Montréal.
G. Joret is a F.R.S.-FNRS Research Fellow. 相似文献
4.
Céline Engelbeen Samuel Fiorini Antje Kiesel 《Journal of Combinatorial Optimization》2011,22(4):609-629
In this paper we consider the following closest vector problem. We are given a set of 0–1 vectors, the generators, an integer vector, the target vector, and a nonnegative integer C. Among all vectors that can be written as nonnegative integer linear combinations of the generators, we seek a vector whose
ℓ
∞-distance to the target vector does not exceed C, and whose ℓ
1-distance to the target vector is minimum. 相似文献
5.
Jean Cardinal Erik D. Demaine Samuel Fiorini Gwenaël Joret Ilan Newman Oren Weimann 《Journal of Combinatorial Optimization》2013,25(1):19-46
The Stackelberg Minimum Spanning Tree Game is a two-level combinatorial pricing problem played on a graph representing a network. Its edges are colored either red or blue, and the red edges have a given fixed cost, representing the competitor’s prices. The first player chooses an assignment of prices to the blue edges, and the second player then buys the cheapest spanning tree, using any combination of red and blue edges. The goal of the first player is to maximize the total price of purchased blue edges. We study this problem in the cases of planar and bounded-treewidth graphs. We show that the problem is NP-hard on planar graphs but can be solved in polynomial time on graphs of bounded treewidth. 相似文献
1