An official website of the United States government
We study two biased Maker-Breaker games played on the complete digraph $$\vec{K}_n$$. In the strong connectivity game, Maker wants to build a strongly connected subgraph. We determine the asymptotic optimal bias for this game viz. $$\frac{n}{\log n}$$. In the Hamiltonian game, Maker wants to build a Hamiltonian subgraph. We determine the asymptotic optimal bias for this game up to a constant factor.
more »
« less
This content will become publicly available on April 11, 2026
Weighted Tree Games
We consider a variation on Maker-Breaker games on graphs or digraphs where the edges have random costs. We assume that Maker wishes to choose the edges of a spanning tree, but wishes to minimise his cost. Meanwhile Breaker wants to make Maker's cost as large as possible.
more »
« less
- Award ID(s):
- 1952285
- PAR ID:
- 10596453
- Publisher / Repository:
- Free journal network
- Date Published:
- Journal Name:
- The Electronic Journal of Combinatorics
- Volume:
- 32
- Issue:
- 2
- ISSN:
- 1077-8926
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
An experimental study of the dynamics and droplet production in three mechanically generated plunging breaking waves is presented in this two-part paper. In the present paper (Part 1), the dynamics of the three breakers are studied through measurements of the evolution of their free surface profiles during 10 repeated breaking events for each wave. The waves are created from dispersively focused wave packets generated with three wave maker motions that differ primarily by small changes in their overall amplitude. Breaker profiles are measured with a cinematic laser-induced fluorescence technique covering a streamwise region of approximately one breaker wavelength and over a time of 3.4 breaker periods. The aligned profile data is used to create spatio-temporal maps of the ensemble average surface height and the standard deviation of both the local normal distance and the local arc length relative to the instantaneous mean profile. It is found that the mean and standard deviation maps contain strongly correlated localized features and indicate that the transition from laminar to turbulent flow is a highly repeatable process. Regions of high standard deviation include the splash created by the plunging jet impact and subsequent splash impacts at the front of the breaking region as well as the site where the air pocket entrained under the plunging jet at the moment of jet tip impact comes to the surface and pops. In Part 2 (Erininet al., J. Fluid Mech., vol. 967, 2023, A36), these features are used to interpret various features of the distributions of droplet number, diameter and velocity.more » « less
-
This paper develops competitive bidding strategies for an online linear optimization problem with inventory management constraints in both cost minimization and profit maximization settings. In the minimization problem, a decision maker should satisfy its time-varying demand by either purchasing units of an asset from the market or producing them from a local inventory with limited capacity. In the maximization problem, a decision maker has a time-varying supply of an asset that may be sold to the market or stored in the inventory to be sold later. In both settings, the market price is unknown in each timeslot and the decision maker can submit a finite number of bids to buy/sell the asset. Once all bids have been submitted, the market price clears and the amount bought/sold is determined based on the clearing price and submitted bids. From this setup, the decision maker must minimize/maximize their cost/profit in the market, while also devising a bidding strategy in the face of an unknown clearing price. We propose DEMBID and SUPBID, two competitive bidding strategies for these online linear optimization problems with inventory management constraints for the minimization and maximization setting respectively. We then analyze the competitive ratios of the proposed algorithms and show that the performance of our algorithms approaches the best possible competitive ratio as the maximum number of bids increases. As a case study, we use energy data traces from Akamai data centers, renewable outputs from NREL, and energy prices from NYISO to show the effectiveness of our bidding strategies in the context of energy storage management for a large energy customer participating in a real-time electricity market.more » « less
-
null (Ed.)We consider a logit model-based framework for modeling joint pricing and assortment decisions that take into account customer features. This model provides a significant advantage when one has insufficient data for any one customer and wishes to generalize learning about one customer’s preferences to the population. Under this model, we study the statistical learning task of model fitting from a static store of precollected customer data. This setting, in contrast to the popular learning and earning paradigm, represents the situation many business teams encounter in which their data collection abilities have outstripped their data analysis capabilities. In this learning setting, we establish finite-sample convergence guarantees on the model parameters. The parameter convergence guarantees are then extended to out-of-sample performance guarantees in terms of revenue, in the form of a high-probability bound on the gap between the expected revenue of the best action taken under the estimated parameters and the revenue generated by a decision maker with full knowledge of the choice model. We further discuss practical implications of these bounds. We demonstrate the personalization approach using ticket purchase data from an airline carrier. This paper was accepted by J. George Shanthikumar, special issue on data-driven prescriptive analyticsmore » « less
-
null (Ed.)Due to dc microgrid nature, dc fault current has no zero-crossing current and could increase up to a thousand amps. Because of that, a dc circuit breaker (DCCB) with the ultra-fast response and high efficiency is required. Regarding this issue, this paper presents a novel thyristor-based DCCB. Then the optimal values of the proposed DCCB components are obtained by cost-power loss multi-objective optimization method. Finally, to keep the maximum temperature of the thyristor below the maximum allowed value, an optimum forced-air microchannel that has high reliability, low cost, and high efficiency is proposed for the proposed thyristor-based DCCB.more » « less
