Fukunaga, Takuro
Published in
Journal of Combinatorial Optimization

Correlation clustering is an approach for clustering a set of objects from given pairwise information. In this approach, the given pairwise information is usually represented by an undirected graph with nodes corresponding to the objects, where each edge in the graph is assigned a nonnegative weight, and either the positive or negative label. Then,...

Tamaki, Hisao
Published in
Journal of Combinatorial Optimization

Consider a dynamic programming scheme for a decision problem in which all subproblems involved are also decision problems. An implementation of such a scheme is positive-instance driven (PID), if it generates positive subproblem instances, but not negative ones, building each on smaller positive instances. We take the dynamic programming scheme due...

Angel, Eric Bampis, Evripidis Kacem, Fadi Letsios, Dimitrios
Published in
Journal of Combinatorial Optimization

We study the problem of scheduling a set of jobs with release dates, deadlines and processing requirements (or works) on parallel speed scalable processors so as to minimize the total energy consumption. We consider that both preemptions and migrations of jobs are allowed. For this problem, there exists an optimal polynomial-time algorithm which us...

Merabet, Massinissa Molnar, Miklos Durand, Sylvain
Published in
Journal of Combinatorial Optimization

Given a connected edge-weighted graph G and a positive integer B, the degree-constrained minimum spanning tree problem (DCMST) consists in finding a minimum cost spanning tree of G such that the degree of each vertex in the tree is less than or equal to B. This problem, which has been extensively studied over the last few decades, has several pract...

Bougeret, Marin Duvillié, Guillerme Giroudeau, Rodolphe
Published in
Journal of Combinatorial Optimization

In this paper we consider the multidimensional binary vector assignment problem. An input of this problem is defined by m disjoint multisets V1,V2,…,Vm\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidema...

Bendotti, Pascale Fouilhoux, Pierre Rottner, Cécile
Published in
Journal of Combinatorial Optimization

The min-up/min-down unit commitment problem (MUCP) is to find a minimum-cost production plan on a discrete time horizon for a set of fossil-fuel units for electricity production. At each time period, the total production has to meet a forecast demand. Each unit must satisfy minimum up-time and down-time constraints besides featuring production and ...

Ning, Baoling Li, Jianzhong Jiang, Shouxu
Published in
Journal of Combinatorial Optimization

We study two variants of the Balanced Tree Partition (BTP for short) problem, whose goal is to find the minimum number of edges such that a partition of vertices into sets of equal size can be obtained after deleting those edges. We consider the BTP problem over trees with virtual nodes, which is motivated by the real applications in storing tree s...

Dong, Luobing Guo, Qiumin Wu, Weili
Published in
Journal of Combinatorial Optimization

An extremely large corpus with rich acoustic properties is very useful for training new speech recognition and semantic analysis models. However, it also brings some troubles, because the complexity of the acoustic model training usually depends on the size of the corpora. In this paper, we propose a corpora subset selection method considering data...

Nimbhorkar, Prajakta Rameshwar, V. Arvind
Published in
Journal of Combinatorial Optimization

We consider the problem of matching applicants to posts where applicants have preferences over posts. Thus the input to our problem is a bipartite graph G=(A∪P,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength...

Arseneva, Elena Papadopoulou, Evanthia
Published in
Journal of Combinatorial Optimization

The Hausdorff Voronoi diagram of clusters of points in the plane is a generalization of Voronoi diagrams based on the Hausdorff distance function. Its combinatorial complexity is O(n+m)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepack...