We consider a seller with an unlimited supply of a single good, who is faced with a stream of $T$ buyers. Each buyer has a window of time in which she would like to purchase, and would buy at the lowest price in that window, provided that this price is lower than her private value (and otherwise, would not buy at all). In this setting, we give an algorithm that attains $O(T^{2/3})$ regret over any sequence of $T$ buyers with respect to the best fixed price in hindsight, and prove that no algorithm can perform better in the worst case.

Previous research in Artificial Intelligence has identified the possibility of simplifying planning problems via the identification and exploitation of symmetries. We advance the state of the art in algorithms that exploit symmetry in planning problems by generalizing previous approaches, and applying symmetry reductions to state-based planners. We suggest several algorithms for symmetry exploitation in state-based search, but also provide a comprehensive view through which additional algorithms can be developed and fine-tuned. We evaluate our approach to symmetry exploitation on instances from previous planning competitions, and demonstrate that our algorithms significantly improve the solution time of instances with symmetries.

However, there are many domains, work that is perhaps closest to ours is the "dead-end heuristic" such as map-based searches (common in GPS navigation, introduced by Björnsson and Halldórsson (2006). They computer games, and robotics) where the entire use a preprocessing phase to identify areas that are deadends, state-space is given explicitly. Optimal paths for such domains and create an abstract graph whose nodes are these can be found relatively quickly with simple heuristics, areas. Initially, the search is performed on the abstracted especially when compared to the time it takes to explore graph. The areas that were not visited during the search exponentially large combinatorial problems. Relative on the abstracted graph are then ignored when the search is quickness, however, might still not be fast enough in certain performed in the original search space. In addition to identifying real-time applications, where further improvement towards dead-ends, our approach also identifies (and prunes, high-speed performance is especially valued.

Previous work on machine scheduling has considered the case of agents who control the scheduled jobs and attempt to minimize their own completion time. We argue that in cloud and grid computing settings, different machines cannot be considered to be fully cooperative as they may belong to competing economic entities, and that agents can easily move their jobs between competing providers. We therefore consider a setting in which the machines are also controlled by selfish agents, and attempt to maximize their own gains by strategically selecting their scheduling policy. We analyze the equilibria that arise due to competition in this 2-sided setting. In particular, not only do we require that the jobs will be in equilibrium with one another, but also that the schedulers' policies will be in equilibrium. We also consider different mixtures of classic deterministic scheduling policies and random scheduling policies.