Minimizing Flow Time in the Wireless Gathering Problem (Articolo in rivista)

Type

• Prodotto della ricerca (Classe)
• Articolo in rivista (Classe)

Label

• Minimizing Flow Time in the Wireless Gathering Problem (Articolo in rivista) (literal)

Anno

• 2011-01-01T00:00:00+01:00 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi

• 10.1145/1978782.1978788 (literal)

Alternative label

• Bonifaci, V.; Korteweg, P.; Marchetti Spaccamela, A.; Stougie, L. (2011)
  Minimizing Flow Time in the Wireless Gathering Problem
  in ACM transactions on algorithms
  (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

• Bonifaci, V.; Korteweg, P.; Marchetti Spaccamela, A.; Stougie, L. (literal)

Pagina inizio

• 33:1 (literal)

Pagina fine

• 33:20 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume

• 7 (literal)

Rivista

• ACM transactions on algorithms (Rivista)

Note

• Scopu (literal)
• ISI Web of Science (WOS) (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni

• Max Planck Institute for Informatics, Saarbruecken, Germany Eindhoven University of Technology, the Netherlands Sapienza University of Rome, Italy Eindhoven University of Technology, the Netherlands (literal)

Titolo

• Minimizing Flow Time in the Wireless Gathering Problem (literal)

Abstract

• We address the problem of efficient data gathering in a wireless network through multihop communication. We focus on two objectives related to flow times, that is, the times spent by data packets in the system: minimization of the maximum flow time and minimization of the average flow time of the packets. For both problems we prove that, unless P = NP, no polynomial-time algorithm can approximate the optimal solution within a factor less than Omega(m(1-epsilon)) for any 0 < epsilon < 1, where m is the number of packets. We then assess the performance of two natural algorithms by proving that their cost remains within the optimal cost of the respective problem if we allow the algorithms to transmit data at a speed 5 times higher than that of the optimal solutions to which we compare them. (literal)

Prodotto di

• Istituto di analisi dei sistemi ed informatica \"Antonio Ruberti\" (IASI) (Istituto)
• Controllo e Ottimizzazione di Sistemi Complessi (ICT.P11.005.001) (Modulo)

Autore CNR

• VINCENZO BONIFACI (Unità di personale interno)

Incoming links:

Prodotto

• Istituto di analisi dei sistemi ed informatica \"Antonio Ruberti\" (IASI) (Istituto)
• Controllo e Ottimizzazione di Sistemi Complessi (ICT.P11.005.001) (Modulo)

Autore CNR di

• VINCENZO BONIFACI (Unità di personale interno)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi

• ACM transactions on algorithms (Rivista)