Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

In an instance of the weighted Nash Social Welfare problem, we are given a set of m indivisible items, G, and n agents, A, where each agent i in A has a valuation v_ij ≥ 0 for each item j in G. In addition, every agent i has a nonnegative weight w_i such that the weights collectively sum up to 1. The goal is to find an assignment of items to players that maximizes the weighted geometric mean of the valuation received by the players. When all the weights are equal, the problem reduces to the classical Nash Social Welfare problem, which has recently received much attention. In this work, we present an approximation algorithm whose approximation depends on the KLdivergence between the weight distribution and the uniform distribution. We generalize the convex programming relaxations for the symmetric variant of Nash Social Welfare presented in [CDG+17, AGSS17] to two different mathematical programs. The first program is convex and is necessary for computational efficiency, while the second program is a nonconvex relaxation that can be rounded efficiently. The approximation factor derives from the difference in the objective values of the convex and nonconvex relaxation.more » « lessFree, publiclyaccessible full text available January 7, 2025

Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics [Puk06], convex geometry [Kha96], fair allocations [AGSS16], combinatorics [AGV18], spectral graph theory [NST19a], network design, and random processes [KT12]. In an instance of a determinant maximization problem, we are given a collection of vectors U = {v1, . . . , vn} ⊂ Rd , and a goal is to pick a subset S ⊆ U of given vectors to maximize the determinant of the matrix ∑i∈S vivi^T. Often, the set S of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint (S ≤ k) or matroid constraint (S is a basis of a matroid defined on the vectors). In this paper, we give a polynomialtime deterministic algorithm that returns a r O(r)approximation for any matroid of rank r ≤ d. This improves previous results that give e O(r^2)approximation algorithms relying on e^O(r)approximate estimation algorithms [NS16, AG17,AGV18, MNST20] for any r ≤ d. All previous results use convex relaxations and their relationship to stable polynomials and strongly logconcave polynomials. In contrast, our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improve any solution by finding an alternating negative cycle in the exchange graph defined by the matroids. While the det(.) function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm.more » « less

Murphy, B. (Ed.)A key form of scientific literacy is being able to leverage the knowledge, practices, and commitments of ethical science to everyday civic matters of social consequence. Learning how to engage in civic life in equityfocused ways needs to be intertwined with learning disciplinary—or transdisciplinary—knowledge and practices. In this article we discuss how an artscience learning program at Science Gallery Dublin in Ireland supported subsequent civic participation by adolescent youth. Using longitudinal case studies of young people, we document how they became agents of change in their homes, schools, and wider communities over several years after participating in the program. This work provides insight into how specific design features of informal learning environments help launch or expand the sciencelinked identities of youth interested in participation in civic life and social action. These cases also illustrate how to develop educational models that support young people to take informed action toward matters of community and environmental consequence, a key aspect of building a more sustainable and thriving future.more » « less

Abstract The XENONnT detector uses the latest and largest liquid xenonbased time projection chamber (TPC) operated by the XENON Collaboration, aimed at detecting Weakly Interacting Massive Particles and conducting other rare event searches.The XENONnT data acquisition (DAQ) system constitutes an upgraded and expanded version of the XENON1T DAQ system.For its operation, it relies predominantly on commercially available hardware accompanied by opensource and customdeveloped software.The three constituent subsystems of the XENONnT detector, the TPC (main detector), muon veto, and the newly introduced neutron veto, are integrated into a single DAQ, and can be operated both independently and as a unified system.In total, the DAQ digitizes the signals of 698 photomultiplier tubes (PMTs), of which 253 from the top PMT array of the TPC are digitized twice, at ×10 and ×0.5 gain.The DAQ for the most part is a triggerless system, reading out and storing every signal that exceeds the digitization thresholds.Customdeveloped software is used to process the acquired data, making it available within ∼30 s for live data quality monitoring and online analyses.The entire system with all the three subsystems was successfully commissioned and has been operating continuously, comfortably withstanding readout rates that exceed ∼500 MB/s during calibration.Livetime during normal operation exceeds 99% and is ∼90% during most highrate calibrations.The combined DAQ system has collected more than 2 PB of both calibration and science data during the commissioning of XENONnT and the first science run.more » « lessFree, publiclyaccessible full text available July 1, 2024

Free, publiclyaccessible full text available July 1, 2024

Free, publiclyaccessible full text available July 1, 2024

Free, publiclyaccessible full text available June 1, 2024