1期

最新文章

• A PTAS for minimizing the total weighted completion time on identical parallel machines AI翻译
  作者：Skutella, M; Woeginger, GJ
  作者单位：Technical University of Berlin; Graz University of Technology
  摘要：We consider the problem of scheduling a set of n jobs on m identical parallel machines so as to minimize the weighted sum of job completion limes. This problem is NP-hard in the strong sense. The best approximation result known so far was a 1/2 (1 + root 2)-approximation algorithm that has been derived by Kawaguchi and Kyan back in 1986. The contribution of this paper is a polynomial time approximation scheme for this setting, which settles a problem that was open for a long time. Moreover, ou...
• The maxmin of recursive games with incomplete information on one side AI翻译
  作者：Rosenberg, D; Vieille, N
  作者单位：Universite Paris 13; Universite de Bordeaux; Institut Polytechnique de Paris; Ecole Polytechnique
• Relaxed most negative cycle and most positive cut canceling algorithms for minimum cost flow AI翻译
  作者：Shigeno, M; Iwata, S; McCormick, ST
  作者单位：University of Tsukuba; University of Osaka; University of British Columbia
  摘要：This paper presents two new scaling algorithms for the minimum cost network flow problem, one a primal cycle canceling algorithm, the other a dual cut canceling algorithm. Both algorithms scale a relaxed optimality parameter, and create a second, inner relaxation. The primal algorithm uses the inner relaxation to cancel a most negative node-disjoint Family of cycles w.r.t. the scaled parameter, the dual algorithm uses it to cancel most positive cuts w.r.t. the scaled parameter. We show that in...