LIVIVO - The Search Portal for Life Sciences

zur deutschen Oberfläche wechseln
Advanced search

Search results

Result 1 - 10 of total 29

Search options

  1. Book ; Online: Hitting Sets when the Shallow Cell Complexity is Small

    Aarts, Sander / Shmoys, David B.

    2023  

    Abstract: The hitting set problem is a well-known NP-hard optimization problem in which, given a set of elements and a collection of subsets, the goal is to find the smallest selection of elements, such that each subset contains at least one element in the ... ...

    Abstract The hitting set problem is a well-known NP-hard optimization problem in which, given a set of elements and a collection of subsets, the goal is to find the smallest selection of elements, such that each subset contains at least one element in the selection. Many geometric set systems enjoy improved approximation ratios, which have recently been shown to be tight with respect to the shallow cell complexity of the set system. The algorithms that exploit the cell complexity, however, tend to be involved and computationally intensive. This paper shows that a slightly improved asymptotic approximation ratio for the hitting set problem can be attained using a much simpler algorithm: solve the linear programming relaxation, take one initial random sample from the set of elements with probabilities proportional to the LP-solution, and, while there is an unhit set, take an additional sample from it proportional to the LP-solution. Our algorithm is a simple generalization of the elegant net-finder algorithm by Nabil Mustafa. To analyze this algorithm for the hitting set problem, we generalize the classic Packing Lemma, and the more recent Shallow Packing Lemma, to the setting of weighted epsilon-nets.

    Comment: Accepted by WAOA2023
    Keywords Computer Science - Computational Geometry
    Publishing date 2023-02-22
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  2. Book ; Online: A min-max theorem for the minimum fleet-size problem

    Ye, Tinghan / Shmoys, David

    2022  

    Abstract: A retrospective fleet-sizing problem can be solved via bipartite matching, where a maximum cardinality matching corresponds to the minimum number of vehicles needed to cover all trips. We prove a min-max theorem on this minimum fleet-size problem: the ... ...

    Abstract A retrospective fleet-sizing problem can be solved via bipartite matching, where a maximum cardinality matching corresponds to the minimum number of vehicles needed to cover all trips. We prove a min-max theorem on this minimum fleet-size problem: the maximum number of pairwise incompatible trips is equal to the minimum fleet size needed.
    Keywords Computer Science - Discrete Mathematics ; Computer Science - Computers and Society
    Publishing date 2022-11-20
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  3. Book ; Online: An Interpretable Determinantal Choice Model for Subset Selection

    Aarts, Sander / Shmoys, David B. / Coy, Alex

    2023  

    Abstract: Understanding how subsets of items are chosen from offered sets is critical to assortment planning, wireless network planning, and many other applications. There are two seemingly unrelated subset choice models that capture dependencies between items: ... ...

    Abstract Understanding how subsets of items are chosen from offered sets is critical to assortment planning, wireless network planning, and many other applications. There are two seemingly unrelated subset choice models that capture dependencies between items: intuitive and interpretable random utility models; and tractable determinantal point processes (DPPs). This paper connects the two. First, all DPPs are shown to be random utility models. Next, a determinantal choice model that enjoys the best of both worlds is specified; the model is shown to subsume logistic regression when dependence is minimal, and MNL when dependence is maximally negative. This makes the model interpretable, while retaining the tractability of DPPs. A simulation study verifies that the model can learn a continuum of negative dependencies from data, and an applied study using original experimental data produces novel insights on wireless interference in LoRa networks.

    Comment: submitted to ICML2023
    Keywords Computer Science - Machine Learning
    Publishing date 2023-02-22
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  4. Book ; Online: Sharing the Cost of IoT Wireless Coverage with a Strengthened Linear Programming Formulation

    Aarts, Sander / Wu, Manxi / Shmoys, David B.

    2023  

    Abstract: Sharing infrastructure between many users is often advantageous, however finding a fair and reasonable way to allocate its cost between its users can be challenging. This is particularly true for LPWANs, a popular Internet of Things solution for ... ...

    Abstract Sharing infrastructure between many users is often advantageous, however finding a fair and reasonable way to allocate its cost between its users can be challenging. This is particularly true for LPWANs, a popular Internet of Things solution for wirelessly connecting devices to the internet. We study cost-allocation of LPWANS using a covering integer program. Standard cost-allocation methods are inapplicable in this model, because the integrality gap of its natural LP-relaxation is unbounded. We overcome this challenge by strengthening the natural LP with knapsack-cover inequalities. Our main result is proving that all dual-feasible solutions to the strengthened LP produce cost-allocations that satisfy the core property. This reduces the problem of finding a cost-allocation to that of finding a strengthened-LP-relative approximation algorithm. Existing algorithms imply improved cost-recovery ratios for families of sparse CIP instances. Finally, we show that the strengthened formulation simplifies and improves the analysis of a cross-monotone cost-allocation mechanism as well.

    Comment: Preprint
    Keywords Computer Science - Computer Science and Game Theory
    Subject code 000 ; 303
    Publishing date 2023-09-28
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  5. Book ; Online: Network Flow Problems with Electric Vehicles

    Pulyassary, Haripriya / Kollias, Kostas / Schild, Aaron / Shmoys, David / Wu, Manxi

    2023  

    Abstract: Electric vehicle (EV) adoption in long-distance logistics faces challenges such as range anxiety and uneven distribution of charging stations. Two pivotal questions emerge: How can EVs be efficiently routed in a charging network considering range limits, ...

    Abstract Electric vehicle (EV) adoption in long-distance logistics faces challenges such as range anxiety and uneven distribution of charging stations. Two pivotal questions emerge: How can EVs be efficiently routed in a charging network considering range limits, charging speeds and prices? And, can the existing charging infrastructure sustain the increasing demand for EVs in long-distance logistics? This paper addresses these questions by introducing a novel theoretical and computational framework to study the EV network flow problems. We present an EV network flow model that incorporates range constraints and nonlinear charging rates, and identify conditions under which polynomial-time solutions can be obtained for optimal single EV routing, maximum flow, and minimum-cost flow problems. Our findings provide insights for optimizing EV routing in logistics, ensuring an efficient and sustainable future.
    Keywords Computer Science - Data Structures and Algorithms
    Subject code 000
    Publishing date 2023-11-08
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  6. Book ; Online: Scheduling with Predictions

    Cho, Woo-Hyung / Henderson, Shane / Shmoys, David

    2022  

    Abstract: There is significant interest in deploying machine learning algorithms for diagnostic radiology, as modern learning techniques have made it possible to detect abnormalities in medical images within minutes. While machine-assisted diagnoses cannot yet ... ...

    Abstract There is significant interest in deploying machine learning algorithms for diagnostic radiology, as modern learning techniques have made it possible to detect abnormalities in medical images within minutes. While machine-assisted diagnoses cannot yet reliably replace human reviews of images by a radiologist, they could inform prioritization rules for determining the order by which to review patient cases so that patients with time-sensitive conditions could benefit from early intervention. We study this scenario by formulating it as a learning-augmented online scheduling problem. We are given information about each arriving patient's urgency level in advance, but these predictions are inevitably error-prone. In this formulation, we face the challenges of decision making under imperfect information, and of responding dynamically to prediction error as we observe better data in real-time. We propose a simple online policy and show that this policy is in fact the best possible in certain stylized settings. We also demonstrate that our policy achieves the two desiderata of online algorithms with predictions: consistency (performance improvement with prediction accuracy) and robustness (protection against the worst case). We complement our theoretical findings with empirical evaluations of the policy under settings that more accurately reflect clinical scenarios in the real world.
    Keywords Computer Science - Data Structures and Algorithms ; Computer Science - Artificial Intelligence ; Computer Science - Machine Learning
    Subject code 006
    Publishing date 2022-12-20
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  7. Book ; Online: Combatting Gerrymandering with Social Choice

    Garg, Nikhil / Gurnee, Wes / Rothschild, David / Shmoys, David

    the Design of Multi-member Districts

    2021  

    Abstract: Every representative democracy must specify a mechanism under which voters choose their representatives. The most common mechanism in the United States -- Winner takes all single-member districts -- both enables substantial partisan gerrymandering and ... ...

    Abstract Every representative democracy must specify a mechanism under which voters choose their representatives. The most common mechanism in the United States -- Winner takes all single-member districts -- both enables substantial partisan gerrymandering and constrains `fair' redistricting, preventing proportional representation in legislatures. We study the design of multi-member districts (MMDs), in which each district elects multiple representatives, potentially through a non-Winner takes all voting rule. We carry out large-scale empirical analyses for the U.S. House of Representatives under MMDs with different social choice functions, under algorithmically generated maps optimized for either partisan benefit or proportionality. Doing so requires efficiently incorporating predicted partisan outcomes -- under various multi-winner social choice functions -- into an algorithm that optimizes over an ensemble of maps. We find that with three-member districts using Single Transferable Vote, fairness-minded independent commissions would be able to achieve proportional outcomes in every state up to rounding, and advantage-seeking partisans would have their power to gerrymander significantly curtailed. Simultaneously, such districts would preserve geographic cohesion, an arguably important aspect of representative democracies. In the process, we advance a rich research agenda at the intersection of social choice and computational gerrymandering.

    Comment: 34 pages
    Keywords Computer Science - Computer Science and Game Theory
    Subject code 320
    Publishing date 2021-07-14
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  8. Book ; Online: GILP

    Robbins, Henry W. / Gutekunst, Samuel C. / Shmoys, David B. / Williamson, David P.

    An Interactive Tool for Visualizing the Simplex Algorithm

    2022  

    Abstract: The Simplex algorithm for solving linear programs-one of Computing in Science & Engineering's top 10 most influential algorithms of the 20th century-is an important topic in many algorithms courses. While the Simplex algorithm relies on intuitive ... ...

    Abstract The Simplex algorithm for solving linear programs-one of Computing in Science & Engineering's top 10 most influential algorithms of the 20th century-is an important topic in many algorithms courses. While the Simplex algorithm relies on intuitive geometric ideas, the computationally-involved mechanics of the algorithm can obfuscate a geometric understanding. In this paper, we present gilp, an easy-to-use Simplex algorithm visualization tool designed to explicitly connect the mechanical steps of the algorithm with their geometric interpretation. We provide an extensive library with example visualizations, and our tool allows an instructor to quickly produce custom interactive HTML files for students to experiment with the algorithm (without requiring students to install anything!). The tool can also be used for interactive assignments in Jupyter notebooks, and has been incorporated into a forthcoming Data Science and Decision Making interactive textbook. In this paper, we first describe how the tool fits into the existing literature on algorithm visualizations: how it was designed to facilitate student engagement and instructor adoption, and how it substantially extends existing algorithm visualization tools for Simplex. We then describe the development and usage of the tool, and report feedback from its use in a course with roughly 100 students. Student feedback was overwhelmingly positive, with students finding the tool easy to use: it effectively helped them link the algebraic and geometrical views of the Simplex algorithm and understand its nuances. Finally, gilp is open-source, includes an extension to visualizing linear programming-based branch and bound, and is readily amenable to further extensions.

    Comment: ACM SIGCSE 2023 Manuscript, 12 pages, 6 figures
    Keywords Computer Science - Human-Computer Interaction ; Computer Science - Graphics ; G.2.0 ; G.4 ; K.3.0
    Publishing date 2022-10-18
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  9. Book ; Online: Modeling the Risk of In-Person Instruction during the COVID-19 Pandemic

    Liu, Brian / Zhang, Yujia / Henderson, Shane G. / Shmoys, David B. / Frazier, Peter I.

    2023  

    Abstract: During the COVID-19 pandemic, implementing in-person indoor instruction in a safe manner was a high priority for universities nationwide. To support this effort at the University, we developed a mathematical model for estimating the risk of SARS-CoV-2 ... ...

    Abstract During the COVID-19 pandemic, implementing in-person indoor instruction in a safe manner was a high priority for universities nationwide. To support this effort at the University, we developed a mathematical model for estimating the risk of SARS-CoV-2 transmission in university classrooms. This model was used to design a safe classroom environment at the University during the COVID-19 pandemic that supported the higher occupancy levels needed to match pre-pandemic numbers of in-person courses, despite a limited number of large classrooms. A retrospective analysis at the end of the semester confirmed the model's assessment that the proposed classroom configuration would be safe. Our framework is generalizable and was also used to support reopening decisions at Stanford University. In addition, our methods are flexible; our modeling framework was repurposed to plan for large university events and gatherings. We found that our approach and methods work in a wide range of indoor settings and could be used to support reopening planning across various industries, from secondary schools to movie theaters and restaurants.
    Keywords Statistics - Applications ; Mathematics - Optimization and Control ; Physics - Physics and Society ; Quantitative Biology - Quantitative Methods ; Statistics - Methodology
    Publishing date 2023-10-06
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  10. Book ; Online: Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem

    An, Hyung-Chan / Kleinberg, Robert / Shmoys, David B.

    2020  

    Abstract: We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem. Given an asymmetric metric cost between n vertices, the problem is to find a Hamiltonian cycle that minimizes its bottleneck (or maximum- ... ...

    Abstract We present the first nontrivial approximation algorithm for the bottleneck asymmetric traveling salesman problem. Given an asymmetric metric cost between n vertices, the problem is to find a Hamiltonian cycle that minimizes its bottleneck (or maximum-length edge) cost. We achieve an O(log n / log log n) approximation performance guarantee by giving a novel algorithmic technique to shortcut Eulerian circuits while bounding the lengths of the shortcuts needed. This allows us to build on a related result of Asadpour, Goemans, M\k{a}dry, Oveis Gharan, and Saberi to obtain this guarantee. Furthermore, we show how our technique yields stronger approximation bounds in some cases, such as the bounded orientable genus case studied by Oveis Gharan and Saberi. We also explore the possibility of further improvement upon our main result through a comparison to the symmetric counterpart of the problem.

    Comment: 16 pages, 3 figures
    Keywords Computer Science - Data Structures and Algorithms ; F.2.2
    Subject code 518
    Publishing date 2020-12-28
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

To top