检索结果-内蒙古大学图书馆

Algorithms for Multiple Drone-Delivery Scheduling Problem (MDSP)

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Anupam, Sagnik Lu, Nicole Sragow, John Department of Electrical Engineering and Computer Science MIT CambridgeMA United States

The Multiple Drone-Delivery Scheduling Problem (MDSP) is a scheduling problem that optimizes the maximum reward earned by a set of m drones executing a sequence of deliveries on a truck delivery route. The current best-known approximation algorithm for the problem is a 4\1 -approximation algorithm developed by Jana and Mandal (2022). In this paper, we propose exact and approximation algorithms for the general MDSP, as well as a unit-cost variant. We first propose a greedy algorithm which we show to be a 1/3 -approximation algorithm for the general MDSP problem formulation, provided the number of conflicting intervals is less than the number of drones. We then introduce a unit-cost variant of MDSP and we devise an exact dynamic programming algorithm that runs in polynomial time when the number of drones m can be assumed to be a constant. Copyright © 2023, The Authors. All rights reserved.

关键词： Drones

Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Srinivasan, Vishwak Wibisono, Andre Wilson, Ashia Department of Electrical Engineering and Computer Science MIT United States Department of Computer Science Yale University United States

We propose a new method called the Metropolis-adjusted Mirror Langevin algorithm for approximate sampling from distributions whose support is a compact and convex set. This algorithm adds an accept-reject filter to the Markov chain induced by a single step of the Mirror Langevin algorithm (Zhang et al., 2020), which is a basic discretisation of the Mirror Langevin dynamics. Due to the inclusion of this filter, our method is unbiased relative to the target, while known discretisations of the Mirror Langevin dynamics including the Mirror Langevin algorithm have an asymptotic bias. For this algorithm, we also give upper bounds for the number of iterations taken to mix to a constrained distribution whose potential is relatively smooth, convex, and Lipschitz continuous with respect to a self-concordant mirror function. As a consequence of the reversibility of the Markov chain induced by the inclusion of the Metropolis-Hastings filter, we obtain an exponentially better dependence on the error tolerance for approximate constrained sampling. We also present numerical experiments that corroborate our theoretical findings. © 2023, CC BY.

关键词： Mirrors

Robust Model Invalidation for Chemical Reaction Networks Using Generalized Moments

学校读者我要写书评

暂无评论

Robust Model Invalidation for Chemical Reaction Networks Usi...

IEEE Conference on Decision and Control

作者： Theodore W. Grunberg Domitilla Del Vecchio Department of Electrical Engineering and Computer Science MIT Cambridge MA USA Department of Mechanical Engineering MIT Cambridge MA USA

Many biomolecular systems can be described by chemical reaction networks, however, there may be several candidate networks based on the known biology for a particular system. Determining which chemical reaction network models are inconsistent with observed data can be done via model invalidation. In this work, we formulate and solve a robust version of the model invalidation problem for the case where only measurements from the stationary distribution are available. This problem corresponds to determining if an observed distribution could have been generated by the given chemical reaction network for some value of the parameters, plus a perturbation of bounded size with respect to total variation distance. The main technical tool we introduce to solve the problem is a set of generalized moments that make the problem amenable to an algorithmic solution.

关键词：

The Effect of the Width of the Incident Pulse to the Dielectric Transition Layer in the Scattering of an Electromagnetic Pulse–a Qubit Lattice Algorithm Simulation

学校读者我要写书评

暂无评论

Communications in Computational Physics 2023年第1期33卷 22-38页

作者： George Vahala Linda Vahala Abhay K.Ram Min Soe Department of Physics William&MaryWilliamsburgVA23185USA Department of Electrical&Computer Engineering Old Dominion UniversityNorfolkVA 12319USA Plasma Science and Fusion Center MITCambridgeMA 02139USA Department of Mathematics and Physical Sciences Rogers State UniversityClaremoreOK 74017USA

The effect of the thickness of the dielectric boundary layer that connects amaterial of refractive index n1 to another of index n2 is considered for the propagation of an electromagnetic pulse.A qubit lattice algorithm(QLA),which consists of a specially chosen non-commuting sequence of collision and streaming operators acting on a basis set of qubits,is theoretically determined that recovers theMaxwell equations to second-order in a small parameterǫ.For very thin but continuous boundary layer the scattering properties of the pulse mimics that found from the Fresnel discontinuous jump conditions for a plane wave-except that the transmission to incident amplitudes are augmented by a factor of√n2/*** the boundary layer becomes thicker one finds deviations away from the discontinuous Fresnel conditions and eventually one approaches the expectedWKB *** there is found a small but unusual dip in part of the transmitted pulse that persists in ***,the QLA simulations still recover the solutions to Maxwell equations even when this parameterǫ→*** examining the pulse propagation in medium n1,ǫcorresponds to the dimensionless speed of the pulse(in lattice units).

关键词： Unitary algorithms qubits Maxwell equations pulse propagation

An Efficient Approach of Brain Tumor Detection & Extraction using BWT with Auto Enhance Technique

学校读者我要写书评

暂无评论

Procedia computer science 2025年 258卷 4105-4116页

作者： Nilesh Bhaskarrao Bahadure Sudhanshu Gonge Jagdish Chandra Patni Bhoomi Shah Nagrajan Raju Prasenjeet D. Patil Department of Computer Science and Engineering School of Technology GSFC University Vadodara Gujarat India Department of Computer Science and Engineering Symbiosis Institute of Technology Symbiosis International (Deemed University) Pune Maharashtra India Department of Computer Science and Engineering Alliance School of Advanced Computing Alliance University Bengaluru India Department of Electrical and Electronics Engineering SASTRA University Thanjavur Tamil Nadu India Department of Computer Science and Engineering MIT ADT University Pune India

Brain tumor detection and extraction of infected areas with utmost accuracy is essential in medical image analysis. Despite ex- cessive research, segmentation operation for brain tumor detection remains an exigent issue because medical images have diverse image contents, non-uniformity object texture, occlusion, image noise, and other factors that consistently influence and affect per- formance analysis. This paper introduces the most efficient brain tumor detection and extraction technique, using Berkely Wavelet Transformation-based segmentation with auto-enhancement techniques. If the input images are too dark or their intensity is not good enough, the auto-enhance technique will automatically adjust the image quality. The extensive experimental analysis and sim- ulation, with a comparison of the results with other state-of-the-art techniques available, prove the significance and effectiveness of the proposed algorithm. The primary intent of this paper is to develop a simple but performance-oriented algorithm for brain tumor detection and extraction, which is suitable for most imaging modalities and gives the best performance even if images are of poor quality.

关键词： Berkeley wavelet transformation enhancement magnetic resonance imaging (MRI) segmentation morphology

Latent Lab: Large Language Models for Knowledge Exploration

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Dunnell, Kevin Painter, Trudy Stoddard, Andrew Lippman, Andy Department of Electrical Engineering and Computer Science MIT United States MIT Media Lab United States

This paper investigates the potential of AI models, particularly large language models (LLMs), to support knowledge exploration and augment human creativity during ideation. We present "Latent Lab" an interactive tool for discovering connections among mit Media Lab research projects, emphasizing "exploration" over search. The work offers insights into collaborative AI systems by addressing the challenges of organizing, searching, and synthesizing content. In a user study, the tool's success was evaluated based on its ability to introduce users to an unfamiliar knowledge base, ultimately setting the groundwork for the ongoing advancement of human-AI knowledge exploration systems. © 2023, CC BY-NC-SA.

关键词： Knowledge based systems

Secretary Problems with Random Number of Candidates: How Prior Distributional Information Helps

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Zhang, Junhui Jaillet, Patrick ORC MIT United States ORC Department of Electrical Engineering and Computer Science MIT United States

We study variants of the secretary problem, where N, the number of candidates, is a random variable, and the decision maker wants to maximize the probability of success – picking the largest number among the N candidates – using only the relative ranks of the candidates revealed so far. We consider three forms of prior information about p, the probability distribution of N . In the full information setting, we assume p to be fully known. In that case, we show that single-threshold type of strategies can achieve 1/e-approximation to the maximum probability of success among all possible strategies. In the upper bound setting, we assume that N ≤ n (or E[N ] ≤ µ), where n (or µ) is known. In that case, we show that randomization over single-threshold type of strategies can achieve the optimal worst case probability of success of log(1n) (or log(1µ) ) asymptotically. Surprisingly, there is a single-threshold strategy (depending on n) that can succeed with probability 2/e2 for all but an exponentially small fraction of distributions supported on [n]. In the sampling setting, we assume that we have access to m samples N (1), . . ., N (m) ∼iid p. In that case, we show that if N ≤ T with probability at least 1 − O(ǫ) for some T ∈ N, m & ǫ12 max(log(1ǫ ), ǫ log(log(ǫT) )) is enough to learn a strategy that is at least ǫ-suboptimal, and we provide a lower bound of Ω(ǫ12 ), showing that the sampling algorithm is optimal when ǫ = O(log log(1T) ). We also discuss applications of some of our techniques to the matroid secretary problems, iid prophet inequalities, and online linear optimization problems when the time horizon N is a random variable. © 2023, CC BY.

关键词： Random variables

ON ACCELERATED PERCEPTRONS AND BEYOND 11

学校读者我要写书评

暂无评论

ON ACCELERATED PERCEPTRONS AND BEYOND

11th International Conference on Learning Representations, ICLR 2023

作者： Wang, Guanghui Hanashiro, Rafael Guha, Etash Abernethy, Jacob College of Computing Georgia Tech AtlantaGA United States Department of Electrical Engineering and Computer Science MIT CambridgeMA United States Google Research AtlantaGA30309 United States

The classical Perceptron algorithm of Rosenblatt can be used to find a linear threshold function to correctly classify n linearly separable data points, assuming the classes are separated by some margin γ > 0. A foundational result is that Perceptron converges after O(1/γ2) iterations. There have been several recent works that managed to improve this rate by a quadratic factor, to O(√log n/γ), with more sophisticated algorithms. In this paper, we unify these existing results under one framework by showing that they can all be described through the lens of solving min-max problems using modern acceleration techniques, mainly through optimistic online learning. We then show that the proposed framework also leads to improved results for a series of problems beyond the standard Perceptron setting. Specifically, a) for the margin maximization problem, we improve the state-of-the-art result from O(log t/t2) to O(1/t2), where t is the number of iterations;b) we provide the first result on identifying the implicit bias property of the classical Nesterov's accelerated gradient descent (NAG) algorithm, and show NAG can maximize the margin with an O(1/t2) rate;c) for the classical p-norm Perceptron problem, we provide an algorithm with (equation presented) convergence rate, while existing algorithms suffer the (equation presented) convergence rate. © 2023 11th International Conference on Learning Representations, ICLR 2023. All rights reserved.

关键词： Gradient methods

Skiing Is Easy, Gymnastics Is Hard: Complexity of Routine Construction in Olympic Sports 11

学校读者我要写书评

暂无评论

Skiing Is Easy, Gymnastics Is Hard: Complexity of Routine Co...

11th International Conference on Fun with Algorithms, FUN 2022

作者： Koppel, James Yu, Yun William Electrical Engineering and Computer Science MIT CambridgeMA United States Computer and Mathematical Sciences University of Toronto at Scarborough Canada Department of Mathematics University of Toronto Canada

ISBN: (纸本)9783959772327

Some Olympic sports, like the marathon, are purely feats of human athleticism. But in others such as gymnastics, athletes channel their athleticism into a routine of skills. In these disciplines, designing the highest-scoring routine can be a challenging problem, because the routines are judged via a combination of artistic merit, which is largely subjective, and technical difficulty, which comes with complicated but objective scoring rules. Notably, since the 2006 Code of Points, FIG (International Gymnastics Federation) has sought to make gymnastics scoring more objective by encoding more of the score in those objective technical side of scoring, and in this paper, we show how that push is reflected in the computational complexity of routine optimization. Here, we analyze the purely-technical component of the scoring rules of routines in 17 different events across 5 Olympic sports. We identify four attributes that classify the common rules found in scoring functions, and, for each combination of attributes, prove hardness results or provide algorithms for designing the highest-scoring routine according to the objective technical component of the scoring functions. Ultimately, we discover that optimal routine construction for events in artistic, rhythmic, and trampoline gymnastics is NP-hard, while optimal routine construction for all other sports is in P. © James Koppel and Yun William Yu.

关键词： Sports