More Like this

1. A deterministic near-linear time approximation scheme for geometric transportation

   https://doi.org/10.1109/FOCS57990.2023.00078  

   Fox, Emily; Lu, Jiashuai (November 2023, IEEE)

   Given a set of points $$P = (P^+ \sqcup P^-) \subset \mathbb{R}^d$$ for some constant $$d$$ and a supply function $$\mu:P\to \mathbb{R}$$ such that $$\mu(p) > 0~\forall p \in P^+$$, $$\mu(p) < 0~\forall p \in P^-$$, and $$\sum_{p\in P}{\mu(p)} = 0$$, the geometric transportation problem asks one to find a transportation map $$\tau: P^+\times P^-\to \mathbb{R}_{\ge 0}$$ such that $$\sum_{q\in P^-}{\tau(p, q)} = \mu(p)~\forall p \in P^+$$, $$\sum_{p\in P^+}{\tau(p, q)} = -\mu(q) \forall q \in P^-$$, and the weighted sum of Euclidean distances for the pairs $$\sum_{(p,q)\in P^+\times P^-}\tau(p, q)\cdot ||q-p||_2$$ is minimized. We present the first deterministic algorithm that computes, in near-linear time, a transportation map whose cost is within a $$(1 + \varepsilon)$$ factor of optimal. More precisely, our algorithm runs in $$O(n\varepsilon^{-(d+2)}\log^5{n}\log{\log{n}})$$ time for any constant $$\varepsilon > 0$$. While a randomized $$n\varepsilon^{-O(d)}\log^{O(d)}{n}$$ time algorithm for this problem was discovered in the last few years, all previously known deterministic $$(1 + \varepsilon)$$-approximation algorithms run in~$$\Omega(n^{3/2})$$ time. A similar situation existed for geometric bipartite matching, the special case of geometric transportation where all supplies are unit, until a deterministic $$n\varepsilon^{-O(d)}\log^{O(d)}{n}$$ time $$(1 + \varepsilon)$$-approximation algorithm was presented at STOC 2022. Surprisingly, our result is not only a generalization of the bipartite matching one to arbitrary instances of geometric transportation, but it also reduces the running time for all previously known $$(1 + \varepsilon)$$-approximation algorithms, randomized or deterministic, even for geometric bipartite matching. In particular, we give the first $$(1 + \varepsilon)$$-approximate deterministic algorithm for geometric bipartite matching and the first $$(1 + \varepsilon)$$-approximate deterministic or randomized algorithm for geometric transportation with no dependence on $$d$$ in the exponent of the running time's polylog. As an additional application of our main ideas, we also give the first randomized near-linear $$O(\varepsilon^{-2} m \log^{O(1)} n)$$ time $$(1 + \varepsilon)$$-approximation algorithm for the uncapacitated minimum cost flow (transshipment) problem in undirected graphs with arbitrary \emph{real} edge costs. 

   more » « less
2. Historical road network statistics for core-based statistical areas in the U.S. (1900 - 2010)

   https://doi.org/10.6084/m9.figshare.19584088.v1  

   Burghardt, Keith; Uhl, Johannes H. (January 2022, figshare)

   Tabulated statistics of road networks at the level of intersections and for built-up areas for each decade from 1900 to 2010, and for 2015, for each core-based statistical area (CBSA, i.e., metropolitan and micropolitan statistical area) in the conterminous United States. These areas are derived from historical road networks developed by Johannes Uhl. See Burghardt et al. (2022) for details on the data processing.  Spatial coverage: all CBSAs that are covered by the HISDAC-US historical settlement layers. This dataset includes around 2,700 U.S. counties. In the remaining counties, construction year coverage in the underlying ZTRAX data (Zillow Transaction and Assessment Dataset) is low. See Uhl et al. (2021) for details. All data created by Keith A. Burghardt, USC Information Sciences Institute, USA Codebook: these CBSA statistics are stratified by degree of aggregation. - CBSA_stats_diffFrom1950: Change in CBSA-aggregated patch statistics between 1950 and 2015 - CBSA_stats_by_decade: CBSA-aggregated patch statistics for each decade from 1900-2010 plus 2015 - CBSA_stats_by_decade: CBSA-aggregated cumulative patch statistics for each decade from 1900-2010 plus 2015. All roads created up to a given decade are used for calculating statistics. - Patch_stats_by_decade: Individual patch statistics for each decade from 1900-2010 plus 2015 - Patch_stats_by_decade: Individual cumulative patch statistics for each decade from 1900-2010 plus 2015. All roads created up to a given decade are used for calculating statistics. The statistics are the following: msaid: CBSA codeid: (if patch statistics) arbitrary int unique to each patch within the CBSA that yearyear: year of statisticspop: population within all CBSA countiespatch_bupr: built up property records (BUPR) within a patch (or sum of patches within CBSA)patch_bupl: built up property l (BUPL) within a patch (or sum of patches within CBSA)patch_bua: built up area (BUA) within a patch (or sum of patches within CBSA)all_bupr: Same as above but for all data in 2015 regardless of whether properties were in patchesall_bupl: Same as above but for all data in 2015 regardless of whether properties were in patchesall_bua: Same as above but for all data in 2015 regardless of whether properties were in patchesnum_nodes: number of nodes (intersections)num_edges: number of edges (roads between intersections)distance: total road length in kmk_mean: mean number of undirected roads per intersectionk1: fraction of nodes with degree 1k4plus: fraction of nodes with degree 4+bearing: histogram of different bearings between intersectionsentropy: entropy of bearing histogrammean_local_gridness: Griddedness used in textmean_local_gridness_max: Same as griddedness used in text but assumes we can have up to 3 quadrilaterals for degree 3 (maximum possible, although intersections will not necessarily create right angles) Code available at https://github.com/johannesuhl/USRoadNetworkEvolution. References: Burghardt, K., Uhl, J., Lerman, K.,  & Leyk, S. (2022). Road Network Evolution in the Urban and Rural  United States Since 1900. Computers, Environment and Urban Systems. 

   more » « less
3. The eigensplitting of the fiber of the cyclotomic trace for the sphere spectrum

   https://doi.org/10.1090/tran/8822  

   Blumberg, Andrew; Mandell, Michael (January 2022, Transactions of the American Mathematical Society)

   Let p ∈ Z p\in {\mathbb {Z}} be an odd prime. We show that the fiber sequence for the cyclotomic trace of the sphere spectrum S {\mathbb {S}} admits an “eigensplitting” that generalizes known splittings on K K -theory and T C TC . We identify the summands in the fiber as the covers of Z p {\mathbb {Z}}_{p} -Anderson duals of summands in the K ( 1 ) K(1) -localized algebraic K K -theory of Z {\mathbb {Z}} . Analogous results hold for the ring Z {\mathbb {Z}} where we prove that the K ( 1 ) K(1) -localized fiber sequence is self-dual for Z p {\mathbb {Z}}_{p} -Anderson duality, with the duality permuting the summands by i ↦ p − i i\mapsto p-i (indexed mod p − 1 p-1 ). We explain an intrinsic characterization of the summand we call Z Z in the splitting T C ( Z ) p ∧ ≃ j ∨ Σ j ′ ∨ Z TC({\mathbb {Z}})^{\wedge }_{p}\simeq j \vee \Sigma j’\vee Z in terms of units in the p p -cyclotomic tower of Q p {\mathbb {Q}}_{p} . 

   more » « less
4. Providing tailored reflection instructions in collaborative learning using large language models

   https://doi.org/10.1111/bjet.13548  

   Naik, Atharva; Yin, Jessica_Ruhan; Kamath, Anusha; Ma, Qianou; Wu, Sherry_Tongshuang; Murray, R_Charles; Bogart, Christopher; Sakr, Majd; Rose, Carolyn_P (December 2024, British Journal of Educational Technology)

   AbstractThe relative effectiveness of reflection either through student generation of contrasting cases or through provided contrasting cases is not well‐established for adult learners. This paper presents a classroom study to investigate this comparison in a college level Computer Science (CS) course where groups of students worked collaboratively to design database access strategies. Forty‐four teams were randomly assigned to three reflection conditions ([GEN] directive to generate a contrasting case to the student solution and evaluate their trade‐offs in light of the principle, [CONT] directive to compare the student solution with a provided contrasting case and evaluate their trade‐offs in light of a principle, and [NSI] a control condition with a non‐specific directive for reflection evaluating the student solution in light of a principle). In the CONT condition, as an illustration of the use of LLMs to exemplify knowledge transformation beyond knowledge construction in the generation of an automated contribution to a collaborative learning discussion, an LLM generated a contrasting case to a group's solution to exemplify application of an alternative problem solving strategy in a way that highlighted the contrast by keeping many concrete details the same as those the group had most recently collaboratively constructed. While there was no main effect of condition on learning based on a content test, low‐pretest student learned more from CONT than GEN, with NSI not distinguishable from the other two, while high‐pretest students learned marginally more from the GEN condition than the CONT condition, with NSI not distinguishable from the other two. Practitioner notesWhat is already known about this topicReflection during or even in place of computer programming is beneficial for learning of principles for advanced computer science when the principles are new to students.Generation of contrasting cases and comparing contrasting cases have both been demonstrated to be effective as opportunities to learn from reflection in some contexts, though questions remain about ideal applicability conditions for adult learners.Intelligent conversational agents can be used effectively to deliver stimuli for reflection during collaborative learning, though room for improvement remains, which provides an opportunity to demonstrate the potential positive contribution of large language models (LLMs).What this paper addsThe study contributes new knowledge related to the differences in applicability conditions between generation of contrasting cases and comparison across provided contrasting cases for adult learning.The paper presents an application of LLMs as a tool to provide contrasting cases tailored to the details of actual student solutions.The study provides evidence from a classroom intervention study for positive impact on student learning of an LLM‐enabled intervention.Implications for practice and/or policyAdvanced computer science curricula should make substantial room for reflection alongside problem solving.Instructors should provide reflection opportunities for students tailored to their level of prior knowledge.Instructors would benefit from training to use LLMs as tools for providing effective contrasting cases, especially for low‐prior‐knowledge students. 

   more » « less
5. Computing the Caratheodory Number of a Point

   Bereg, Sergey; Haghpanah, Mohammadreza (August 2020, Canadian Conference on Computational Geometry)

   Caratheodory’s theorem says that any point in the convex hull of a set $$P$$ in $R^d$ is in the convex hull of a subset $P'$ of $$P$$ such that $$|P'| \le d + 1$$. For some sets P, the upper bound d + 1 can be improved. The best upper bound for P is known as the Caratheodory number [2, 15, 17]. In this paper, we study a computational problem of finding the smallest set $P'$ for a given set $$P$$ and a point $$p$$. We call the size of this set $P'$, the Caratheodory number of a point p or CNP. We show that the problem of deciding the Caratheodory number of a point is NP-hard. Furthermore, we show that the problem is k-LDT-hard. We present two algorithms for computing a smallest set $P'$, if CNP= 2,3. Bárány [1] generalized Caratheodory’s theorem by using d+1 sets (colored sets) such that their convex hulls intersect. We introduce a Colorful Caratheodory number of a point or CCNP which can be smaller than d+1. Then we extend our results for CNP to CCNP. 

   more » « less