More Like this

1. Online Submodular Maximization via Online Convex Optimization

   https://doi.org/10.1609/aaai.v38i13.29425  

   Si_Salem, Tareq; Özcan, Gözde; Nikolaou, Iasonas; Terzi, Evimaria; Ioannidis, Stratis (March 2024, Proceedings of the AAAI Conference on Artificial Intelligence)

   We study monotone submodular maximization under general matroid constraints in the online setting. We prove that online optimization of a large class of submodular functions, namely, threshold potential functions, reduces to online convex optimization (OCO). This is precisely because functions in this class admit a concave relaxation; as a result, OCO policies, coupled with an appropriate rounding scheme, can be used to achieve sublinear regret in the combinatorial setting. We also show that our reduction extends to many different versions of the online learning problem, including the dynamic regret, bandit, and optimistic-learning settings. 

   more » « less
2. Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods

   Tarzanagh, Davoud Ataee; Nazari, Parvin; Hou, Bojian; Shen, Li; Balzano, Laura (May 2024, Proceedings of the 27th International Conference on Artifi- cial Intelligence and Statistics (AISTATS) 2024,)
3. Online Illegal Cryptomarkets

   https://doi.org/10.1146/annurev-soc-090523-052916  

   Haynie, Dana L; Duxbury, Scott W (May 2024, Annual Review of Sociology)

   Cryptomarkets—online markets for illegal goods—have revolutionized the illegal drug trade, constituting about 10% of all drug trades and attracting users to a greater variety and more addictive substances than available in offline drug markets. This review introduces the burgeoning area of sociology research on illegal cryptomarkets, particularly in the realm of drug trade. We emphasize the expanding role of illicit online trade and its relevance for understanding broader exchange challenges encountered in all illegal trade settings. Examining the effects of online illegal trade on consumption and supply-side policing, we also discuss the harm and potential benefits of moving drug exchange from offline to online markets. We argue for a network perspective's efficacy in this research domain, emphasizing its relevance in assessing trade and discussion networks, technical innovation, and market evolution and vulnerabilities. Concluding, we outline future research areas, including market culture, failure, and the impact of online illegal trade on stratification. 

   more » « less
4. Online facility assignment

   https://doi.org/10.1016/j.tcs.2019.08.011  

   Ahmed, Abu Reyan; Saidur Rahman, Md.; Kobourov, Stephen (February 2020, Theoretical Computer Science)
5. Online Facility Assignment

   Ahmed, Reyan; Rahman, Saidur; Kobourov, Stephen (January 2018, Walcom)

   We consider the online facility assignment problem, with a set of facilities F of equal capacity l in metric space and customers arriving one by one in an online manner. We must assign customer ci to facility fj before the next customer ci+1 arrives. The cost of this assignment is the distance between ci and fj. The total number of customers is at most |F|l and each customer must be assigned to a facility. The objective is to minimize the sum of all assignment costs. We first consider the case where facilities are placed on a line so that the distance between adjacent facilities is the same and customers appear anywhere on the line. We describe a greedy algorithm with competitive ratio 4|F| and another one with competitive ratio |F|. Finally, we consider a variant in which the facilities are placed on the vertices of a graph and two algorithms in that setting. 

   more » « less