SwePub
Sök i SwePub databas

  Utökad sökning

Träfflista för sökning "WFRF:(Mastrolilli Monaldo) "

Sökning: WFRF:(Mastrolilli Monaldo)

  • Resultat 1-2 av 2
Sortera/gruppera träfflistan
   
NumreringReferensOmslagsbildHitta
1.
  • Ambuehl, Christoph, et al. (författare)
  • INAPPROXIMABILITY RESULTS FOR MAXIMUM EDGE BICLIQUE, MINIMUM LINEAR ARRANGEMENT, AND SPARSEST CUT
  • 2011
  • Ingår i: SIAM journal on computing (Print). - : Society for Industrial & Applied Mathematics (SIAM). - 0097-5397 .- 1095-7111. ; 40:2, s. 567-596
  • Tidskriftsartikel (refereegranskat)abstract
    • We consider the Minimum Linear Arrangement problem and the (Uniform) Sparsest Cut problem. So far, these two notorious NP-hard graph problems have resisted all attempts to prove inapproximability results. We show that they have no polynomial time approximation scheme, unless NP-complete problems can be solved in randomized subexponential time. Furthermore, we show that the same techniques can be used for the Maximum Edge Biclique problem, for which we obtain a hardness factor similar to previous results but under a more standard assumption.
  •  
2.
  • Mastrolilli, Monaldo, et al. (författare)
  • Minimizing the sum of weighted completion times in a concurrent open shop
  • 2010
  • Ingår i: Operations Research Letters. - : Elsevier BV. - 0167-6377 .- 1872-7468. ; 38:5, s. 390-395
  • Tidskriftsartikel (refereegranskat)abstract
    • We study minimizing the sum of weighted completion times in a concurrent open shop. We give a primal-dual 2-approximation algorithm for this problem. We also show that several natural linear programming relaxations for this problem have an integrality gap of 2. Finally, we show that this problem is inapproximable within a factor strictly less than 6/5 if not equal NP, or strictly less than 4/3 if the Unique Games Conjecture also holds. (C) 2010 Elsevier B.V. All rights reserved.
  •  
Skapa referenser, mejla, bekava och länka
  • Resultat 1-2 av 2
Typ av publikation
tidskriftsartikel (2)
Typ av innehåll
refereegranskat (2)
Författare/redaktör
Svensson, Ola (2)
Mastrolilli, Monaldo (2)
Ambuehl, Christoph (1)
Queyranne, Maurice (1)
Schulz, Andreas S. (1)
Uhan, Nelson A. (1)
Lärosäte
Kungliga Tekniska Högskolan (2)
Språk
Engelska (2)
Forskningsämne (UKÄ/SCB)
Naturvetenskap (1)

År

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Stäng

Kopiera och spara länken för att återkomma till aktuell vy