Paper Info
Title
Statistical Analysis of Algorithms: A Case Study of Market-Clearing Mechanisms in the Power Industry
Abstract
Abstract We carry out a detailed empirical analysis of simple heuristics and provable algorithms for bilateral contract - satisfaction problems Such problems arise due to the proposed deregulation of the electric utility industry in the USA Given a network and a (multi)set of pairs of vertices (contracts) with associated demands, the goal is to find the maximum number of simultaneously satisfiable contracts Four di$erent algorithms (three heuristics and a provable approximation algorithm) are considered and their performance is studied empirically in fairly realistic settings us - ing rigorous statistical analysis For this purpose, we use an approximate electrical transmission network in the state of Colorado Our experiments are based on the statistical technique Analysis of Variance (ANOVA), and show that the three heuristics outperform a theoretically better algorithm We also test the algorithms on four types of scenarios that are likely to occur in a deregulated marketplace Our results show that the networks that are adequate in a regulated marketplace might be inadequate for satisfying all the bilateral contracts in a deregulated industry
Year
Venue
Keywords
2003
J. Graph Algorithms Appl.
statistical analysis,satisfiability,analysis of variance
Field
DocType
Volume
Approximation algorithm,Mathematical optimization,Market clearing,Electric utility,Vertex (geometry),Computer science,Algorithm,Electric power transmission,Electric power industry,Heuristics,Statistical theory
Journal
7
Issue
Citations 
PageRank 
1
2
0.46
References 
Authors
3
9
Name
Order
Citations
PageRank
Chris L. Barrett169266.06
Achla Marathe220323.77
Madhav Marathe32775262.17
Doug Cook481.67
Gregory Hicks551.37
Vance Faber667955.50
Aravind Srinivasan73531291.42
Yoram J. Sussmann811416.70
Heidi Thornquist961.64