4.5 Article

An Exponential Improvement on the MST Heuristic for Minimum Energy Broadcasting in Ad Hoc Wireless Networks

Journal

IEEE-ACM TRANSACTIONS ON NETWORKING
Volume 21, Issue 4, Pages 1322-1331

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TNET.2012.2223483

Keywords

Approximation algorithms; broadcasting; energy consumption; wireless networks

Funding

  1. European Union [STREP FP7-258307 EULER]
  2. PRIN 2008 research project COGENT (COmputational and GamE-theoretic aspects of uncoordinated NeTworks)
  3. Italian Ministry of University and Research

Ask authors/readers for more resources

We present a new approximation algorithm for the Minimum Energy Broadcast Routing (MEBR) problem in ad hoc wireless networks that achieves an exponentially better approximation factor compared to the well-known Minimum Spanning Tree (MST) heuristic. Namely, for any instance where a minimum spanning tree of the set of stations is guaranteed to cost at most rho >= 2 times the cost of an optimal solution for MEBR, we prove that our algorithm achieves an approximation ratio bounded by 2ln rho - 2ln 2 + 2. This result is particularly relevant for its consequences on Euclidean instances where we significantly improve previous results. In this respect, our experimental analysis confirms the better performance of the algorithm also in practice.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.5
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

Article Computer Science, Artificial Intelligence

Nash Stable Outcomes in Fractional Hedonic Games: Existence, Efficiency and Computation

Vittorio Bilo, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, Luca Moscardelli

JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH (2018)

Article Computer Science, Theory & Methods

An Almost Ideal Coordination Mechanism for Unrelated Machine Scheduling

Ioannis Caragiannis, Angelo Fanelli

THEORY OF COMPUTING SYSTEMS (2019)

Article Computer Science, Artificial Intelligence

Optimizing positional scoring rules for rank aggregation

Loannis Caragiannis, Xenophon Chatzigeorgiou, George A. Krimpas, Alexandros A. Voudouris

ARTIFICIAL INTELLIGENCE (2019)

Article Computer Science, Artificial Intelligence

On social envy-freeness in multi-unit markets

Michele Flammini, Manuel Mauro, Matteo Tonelli

ARTIFICIAL INTELLIGENCE (2019)

Editorial Material Computer Science, Theory & Methods

Guest Editorial: Special Issue on Algorithmic Game Theory

Vittorio Bilo, Michele Flammini

THEORY OF COMPUTING SYSTEMS (2019)

Article Operations Research & Management Science

The Efficiency of Resource Allocation Mechanisms for Budget-Constrained Users

Ioannis Caragiannis, Alexandros A. Voudouris

Summary: Efficiency of mechanisms for allocating a divisible resource is studied, taking into account users' self-interest and budget constraints. The liquid welfare benchmark is used to analyze the price of anarchy, demonstrating a tight bound of 2 on the liquid price of anarchy for the well-known Kelly mechanism. This result is shown to be essentially optimal among all multiuser resource allocation mechanisms.

MATHEMATICS OF OPERATIONS RESEARCH (2021)

Article Automation & Control Systems

Evaluating approval-based multiwinner voting in terms of robustness to noise

Ioannis Caragiannis, Christos Kaklamanis, Nikos Karanikolas, George A. Krimpas

Summary: Approval-based multiwinner voting rules have gained much attention in the Computational Social Choice literature. To assess their effectiveness, new noise models specifically tailored for approval votes and committees are proposed. Our findings indicate that these voting rules can be robust to reasonable noise, and a hierarchy of rules in terms of their robustness to noise is presented.

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS (2022)

Proceedings Paper Computer Science, Interdisciplinary Applications

Relaxing the Independence Assumption in Sequential Posted Pricing, Prophet Inequality, and Random Matching

Ioannis Caragiannis, Nick Gravin, Pinyan Lu, Zihe Wang

Summary: In this article, three classical settings of optimization under uncertainty are reexamined under the assumption of pairwise independence among random events. The study shows that positive results can still be achieved under these more general assumptions.

WEB AND INTERNET ECONOMICS, WINE 2021 (2022)

Proceedings Paper Computer Science, Interdisciplinary Applications

Computing Envy-Freeable Allocations with Limited Subsidies

Ioannis Caragiannis, Stavros D. Ioannidis

Summary: The problem of minimizing subsidies for envy-freeness is a challenging task, with recent research focusing on designing approximation algorithms due to its NP-hard nature. While for a small number of agents, it is possible to approximate the minimum subsidy amount with a graceful increase in running time, for a superconstant number of agents, both exact computation and approximation are difficult.

WEB AND INTERNET ECONOMICS, WINE 2021 (2022)

Proceedings Paper Computer Science, Artificial Intelligence

On Social Envy-Freeness in Multi-Unit Markets

Michele Flammini, Manuel Mauro, Matteo Tonelli

THIRTY-SECOND AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTIETH INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / EIGHTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE (2018)

Proceedings Paper Automation & Control Systems

Online Coalition Structure Generation in Graph Games

Michele Flammini, Gianpiero Monaco, Luca Moscardelli, Mordechai Shalom, Shmuel Zaks

PROCEEDINGS OF THE 17TH INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS (AAMAS' 18) (2018)

Proceedings Paper Automation & Control Systems

On the Impact of Buyers Preselection in Pricing Problems

Vittorio Bilo, Michele Flammini, Gianpiero Monaco, Luca Moscardelli

PROCEEDINGS OF THE 17TH INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS (AAMAS' 18) (2018)

Proceedings Paper Automation & Control Systems

Computing Approximate Pure Nash Equilibria in Digraph k-Coloring Games

Raffaello Carosi, Michele Flammini, Gianpiero Monaco

AAMAS'17: PROCEEDINGS OF THE 16TH INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS (2017)

Proceedings Paper Computer Science, Artificial Intelligence

Nash Stability in Social Distance Games

Alkida Balliu, Michele Flammini, Giovanna Melideo, Dennis Olivetti

THIRTY-FIRST AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE (2017)

Proceedings Paper Computer Science, Artificial Intelligence

On Pareto Optimality in Social Distance Games

Alkida Balliu, Michele Flammini, Dennis Olivetti

THIRTY-FIRST AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE (2017)

No Data Available