An official website of the United States government
Flexible grid networks need rigorous resource planning to avoid network over-dimensioning and resource over-provisioning. The network must provision the hardware and spectrum resources statically, even for dynamic random bandwidth demands, due to the infrastructure of flexible grid networks, hardware limitations, and reconfiguration speed of the control plane. We propose a flexible online–offline probabilistic (FOOP) algorithm for the static spectrum assignment of random bandwidth demands. The FOOP algorithm considers the probabilistic nature of random bandwidth demands and balances hardware and control plane pressures with spectrum assignment efficiency. The FOOP algorithm uses the probabilistic spectrum Gaussian noise (PSGN) model to estimate the physical-layer impairment (PLI) for random bandwidth traffic. Compared to a benchmark spectrum assignment algorithm and a widely applied PLI estimation model, the proposed FOOP algorithm using the PSGN model saves up to 49% of network resources.
more »
« less
A Randomized Approximation Technique for Resource-Allocation Problems
We develop a rounding method based on random walks in polytopes, which leads to improved approximation algorithms and integrality gaps for several assignment problems that arise in resource allocation and scheduling. In particular, it generalizes the work of Shmoys & Tardos on the generalized assignment problem to the setting where some jobs can be dropped. New concentration bounds for random bipartite matching are developed as well.
more »
« less
- Award ID(s):
- 1749864
- PAR ID:
- 10066178
- Date Published:
- Journal Name:
- Random structures & algorithms
- Volume:
- 52
- ISSN:
- 1098-2418
- Page Range / eLocation ID:
- 680-715
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Random parameter logit models address unobserved preference heterogeneity in discrete choice analysis. The latent class logit model assumes a discrete heterogeneity distribution, by combining a conditional logit model of economic choices with a multinomial logit (MNL) for stochastic assignment to classes. Whereas point estimation of latent class logit models is widely applied in practice, stochastic assignment of individuals to classes needs further analysis. In this paper we analyze the statistical behavior of six competing class assignment strategies, namely: maximum prior MNL probabilities, class drawn from prior MNL probabilities, maximum posterior assignment, drawn posterior assignment, conditional individual-specific estimates, and conditional individual estimates combined with the Krinsky–Robb method to account for uncertainty. Using both a Monte Carlo study and two empirical case studies, we show that assigning individuals to classes based on maximum MNL probabilities behaves better than randomly drawn classes in market share predictions. However, randomly drawn classes have higher accuracy in predicted class shares. Finally, class assignment based on individual-level conditional estimates that account for the sampling distribution of the assignment parameters shows superior behavior for a larger number of choice occasions per individual.more » « less
-
We describe an algorithm to solve the problem of Boolean CNF-Satisfiability when the input formula is chosen randomly. We build upon the algorithms of Schöning 1999 and Dantsin et al. in 2002. The Schöning algorithm works by trying many possible random assignments, and for each one searching systematically in the neighborhood of that assignment for a satisfying solution. Previous algorithms for this problem run in time O(2^(n (1- Ω(1)/k))). Our improvement is simple: we count how many clauses are satisfied by each randomly sampled assignment, and only search in the neighborhoods of assignments with abnormally many satisfied clauses. We show that assignments like these are significantly more likely to be near a satisfying assignment. This improvement saves a factor of 2^(n Ω(lg² k)/k), resulting in an overall runtime of O(2^(n (1- Ω(lg² k)/k))) for random k-SAT.more » « less
-
Deep Reinforcement Learning (DRL) has been shown to be a very powerful technique in recent years on a wide range of applications. Much of the prior DRL work took the online learning approach. However, given the challenges of building accurate simulations for modeling student learning, we investigated applying DRL to induce a pedagogical policy through an offiine approach. In this work, we explored the effectiveness of offiine DRL for pedagogical policy induction in an Intelligent Tutoring System. Generally speaking, when applying offiine DRL, we face two major challenges: one is limited training data and the other is the credit assignment problem caused by delayed rewards. In this work, we used Gaussian Processes to solve the credit assignment problem by estimating the inferred immediate rewards from the final delayed rewards. We then applied the DQN and Double-DQN algorithms to induce adaptive pedagogical strategies tailored to individual students. Our empirical results show that without solving the credit assignment problem, the DQN policy, although better than Double-DQN, was no better than a random policy. However, when combining DQN with the inferred rewards, our best DQN policy can outperform the random yet reasonable policy, especially for students with high pre-test scores.more » « less
-
Throughput extremization is an important facet of performance modeling for low-power wide-area network (LP-WAN) wireless networks (e.g., LoRaWAN) as it provides insight into the best and worst case behavior of the network. Our previous work on throughput extremization established lower and upper bounds on throughput for random access channel assignment over a collision erasure channel in which the lower bound is expressed in terms of the number of radios and sum load on each channel. In this paper the lower bound is further characterized by identifying two local minimizers (a load balanced assignment and an imbalanced assignment) where the decision variables are the number of radios assigned to each channel and the total load on each channel. A primary focus is to characterize how macro-parameters of the optimization, i.e., the total number of radios, their total load, and the minimum load per radio, determine the regions under which each of the local minimizers is in fact the global minimizer.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
