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

Registration of PE segment contour deformations in digital high-speed videos

MEDICAL IMAGE ANALYSIS 2008年第3期12卷 318-334页

作者： Stiglmayr, Michael Schwarz, Raphael Klamroth, Kathrin Leugering, Guenter Lohscheller, Joerg Univ Erlangen Nurnberg Inst Appl Math D-91058 Erlangen Germany Univ Erlangen Nurnberg Dept Phoniatr & Pediat Audiol D-91058 Erlangen Germany

Oncologic therapy of laryngeal cancer may necessitate a total excision of the larynx which results in loss of voice. Voice rehabilitation can be achieved using mucosal tissue vibrations at the upper part of the esophagus which serves as substitute voice generating element (PE segment). The quality of the substitute voice is closely related to vibratory characteristics of the PE segment. By means of a highspeed camera the dynamics of the PE segment can be recorded in real-time. Using image processing the deformations of the PE segment are extracted from the image series as deforming contours. Commonly, the characterization of PE dynamics bases on the spectral analysis of the time varying contour area. However, this constitutes an integral approach which masks most of the specific dynamics of PE deformations. We present an algorithm that automatically registers one segmented contour in a frame of the video sequence to the contour in the next frame to derive discrete 2-D trajectories of PE vibrations. By concatenation of the obtained transformations this approach provides a total registration of PE segment contours. We suggest a mixed-integer programming formulation for the problem that combines an advanced outlier and deformation handling with the introduction of dummy points in regions that newly open up, and that includes normal information in the objective function to avoid unwanted deformations. Numerical experiments show that the implemented alternate convex search algorithm produces robust results which is demonstrated at the example of five high-speed recordings of laryngectomee subjects. (C) 2007 Elsevier B.V. All rights reserved.

关键词： substitute voice PE segment digital high-speed videos point matching shape registration generalized assignment problem 2-D trajectories

来源：评论

学校读者我要写书评

暂无评论

Competence-based assignment of tasks to workers in factories with demand-driven manufacturing

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2021年第2期29卷 553-565页

作者： Staruch, Bozena Staruch, Bogdan Univ Warmia & Mazury Olsztyn Poland

The paper is motivated by real problems concerning tasks assignment to workers in medium-sized upholstered furniture plants managed using the Demand-Driven Manufacturing. Although the methodology was developed for furniture plants it can be applied to other types of production plants. We involve competence coefficients, which describe the level of the worker's skills or capabilities to perform a specific task. The competence coefficients are also used to block the possibility of assigning the given task to a worker that has no skills to do it. Additionally, we involve a dummy worker to the model which guarantees the existence of a solution to the problem. We present and discuss Integer Linear Programming Models for the posted problem that are closely related to the generalized assignment problem. We also discuss the potential use of the presented methodology to solve real-life problems related to production management.

关键词： Tasks assignment Competence coefficient Production planning Demand-driven manufacturing Lean production Kanban Integer linear programming generalized assignment problem Multi-knapsack problem

来源：评论

学校读者我要写书评

暂无评论

Leveraging Parallel Communications for Minimizing Energy Consumption on Smartphones

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2015年第10期26卷 2778-2790页

作者： Conti, Mauro Crispo, Bruno Diodati, Daniele Nurminen, Jukka K. Pinotti, Cristina M. Teemaa, Taavi Univ Padua Dept Math Padua Italy Univ Trento Dept Informat Engn & Comp Sci Trento Italy Univ Perugia Dept Math & Comp Sci I-06100 Perugia Italy Aalto Univ Dept Comp Sci Aalto Finland

Recent energy measurements on smartphones have shown that parallel communications (e.g., data transfer and voice call) require less energy than their stand-alone execution. Guided by these results, we investigate the possibility of scheduling communications in pairs for minimizing the energy consumption. We define two energy optimization problems to postpone delay-tolerant services and perform them in parallel with real-time services in order to save energy. The first problem, called single delay-tolerant assignment (SDA), allows at most one delay-tolerant service to be paired with each real-time service, whereas the second problem, called multiple delay-tolerant assignment (MDA), allows multiple delay-tolerant services to be paired (in different times) with the same real-time service. For the SDA problem, we propose an optimal algorithm. For the MDA problem, which is computationally intractable, we give an approximation algorithm. We evaluate the benefits of the energy-efficient pairing strategy via simulations on synthetic traces. The MDA algorithm can save up to the 60 percent of the energy consumption using 4G network assuming an intensive smartphone usage, while the SDA algorithm saves up to the 20 percent.

关键词： Energy saving smartphones delay-tolerant services parallel communications measurements maximum weighted matching generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

Energy Efficient User Association, Power, and Flow Control in Millimeter Wave Backhaul Heterogeneous Networks

IEEE OPEN JOURNAL OF THE COMMUNICATIONS SOCIETY

引用

IEEE OPEN JOURNAL OF THE COMMUNICATIONS SOCIETY 2020年 1卷 41-59页

作者： Aboagye, Sylvester Ibrahim, Ahmed Ngatched, Telex M. N. Mem Univ Fac Engn & Appl Sci St John NF A1C 5S7 Canada

This paper studies the problem of energy efficiency (EE) maximization via user association, power, and backhaul (BH) flow control in the downlink of millimeter wave BH heterogeneous networks. This problem is mathematically formulated as a mixed-integer non-linear program, which is non-convex. To get a tractable solution, the initial problem is separated into two sub-problems and optimized sequentially. The first is a joint user association and power control sub-problem for the access network (AN) (AN sub-problem). The second is a joint flow and power control sub-problem for the BH network (BH sub-problem). While the BH sub-problem is a convex optimization problem and hence can be efficiently solved, the AN sub-problem assumes the form of a generalized assignment problem, which is known to be NP-hard. To that end, we utilize Lagrangian decomposition to propose two polynomial time solution techniques that obtain a high-quality solution for the AN sub-problem. The first, referred to as Technique A, uses dynamic programming, the subgradient method, and a heuristic. The second, named Technique B, uses the multiplier adjustment method, the sorting algorithm, and a heuristic. Simulation results are used to demonstrate the effectiveness of the proposed energy efficient user association, power, and BH flow control algorithms as compared with benchmark user association schemes that incorporate the BH sub-problem algorithm, in terms of the total AN power, BH power, and overall network (AN plus BH) EE. The computational complexity and practical implementation of the proposed algorithms are discussed.

关键词： Flow control generalized assignment problem Lagrangian multipliers multiplier adjustment method power control subgradient user association

来源：评论

学校读者我要写书评

暂无评论

SCHEDULING OF PROJECT NETWORKS BY JOB assignment

引用

MANAGEMENT SCIENCE 1991年第12期37卷 1590-1602页

作者： DREXL, A UNIV KIEL INST BETRIEBSWIRTSCHAFTSLEHRE OLSHAUSENSTR 40 W-2300 KIEL 1 GERMANY

A recurring problem in project management involves the allocation of scarce resources to the individual jobs comprising the project. In many situations such as audit scheduling, the resources correspond to individuals (skilled labour). This naturally leads to an assignment type project scheduling problem, i.e. a project has to be processed by assigning one of several individuals (resources) to each job. In this paper we consider the nonpreemptive variant of a resource-constrained project job-assignment problem, where job durations as well as costs depend upon the assigned resource. Regarding precedence relations as well as release dates and deadlines, the question arises, to which jobs resources should be assigned in order to minimize overall costs. For solving this time-resource-cost-tradeoff problem we present a hybrid brand and bound/dynamic programming algorithm with a (rather efficient Monte Carlo type) heuristic upper bounding technique as well as various relaxation procedures for determining lower bounds. Computational results are presented as well.

关键词： PROJECT MANAGEMENT RESOURCE CONSTRAINTS AUDIT SCHEDULING generalized assignment problem BRANCH AND BOUND DYNAMIC PROGRAMMING MONTE-CARLO HEURISTIC

来源：评论

学校读者我要写书评

暂无评论

Revenue Maximization and Ex-Post Budget Constraints

引用

ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION 2018年第3-4期6卷 1–19页

作者： Daskalakis, Constantinos Devanur, Nikhil R. Weinberg, S. Matthew MIT 77 Massachusetts Ave Cambridge MA 02139 USA Microsoft Res Redmond WA USA Princeton Univ Princeton NJ 08544 USA 32 Vassar St Cambridge MA 02139 USA Bldg 99 14820 NE 36th St Redmond WA 98052 USA 35 Olden St Princeton NJ 08540 USA

We consider the problem of a revenue-maximizing seller withm items for sale to n additive bidders with hard budget constraints, assuming that the seller has some prior distribution over bidder values and budgets. The prior may be correlated across items and budgets of the same bidder, but is assumed independent across bidders. We target mechanisms that are Bayesian incentive compatible, but that are ex-post individually rational and ex-post budget respecting. Virtually no such mechanisms are known that satisfy all these conditions and guarantee any revenue approximation, even with just a single item. We provide a computationally efficient mechanism that is a 3-approximation with respect to all BIC, ex-post IR, and ex-post budget respecting mechanisms. Note that the problem is NP-hard to approximate better than a factor of 16/15, even in the case where the prior is a point mass. We further characterize the optimal mechanism in this setting, showing that it can be interpreted as a distribution over virtual welfare maximizers. We prove our results by making use of a black-box reduction from mechanism to algorithm design developed by Cai et al. Our main technical contribution is a computationally efficient 3-approximation algorithm for the algorithmic problem that results from an application of their framework to this problem. The algorithmic problem has a mixed-sign objective and is NP-hard to optimize exactly, so it is surprising that a computationally efficient approximation is possible at all. In the case of a single item (m = 1), the algorithmic problem can be solved exactly via exhaustive search, leading to a computationally efficient exact algorithm and a stronger characterization of the optimal mechanism as a distribution over virtual value maximizers.

关键词： Revenue optimization budget constraints virtual welfare generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

A HEURISTIC ALGORITHM FOR THE LOADING problem IN FLEXIBLE MANUFACTURING SYSTEMS

引用

INTERNATIONAL JOURNAL OF FLEXIBLE MANUFACTURING SYSTEMS 1995年第3期7卷 229-254页

作者： KUHN, H 1. IBL und Produktionswirtschaft Albertus-Magnus-Platz Universit?t zu K?ln Seminar für ABWL D-50923 K?ln Germany

The paper considers the loading problem in flexible manufacturing systems (FMSs). This problem involves the assignment to the machine tools of all operations and associated cutting tools required for part types that have been selected to be produced simultaneously. The loading problem is first formulated as a linear mixed 0-1 program with the objective to minimize the greatest workload assigned to each machine. A heuristic procedure is presented in which an assignment of operations to machine tools is obtained by solving a parameterized generalized assignment problem with an objective function that approximates the use of tool slots required by the operations assigned to the machines. The algorithm is coded in FORTRAN and tested on an IBM-compatible personal computer. Computational results are presented for different test problems to demonstrate the efficiency and effectiveness of the suggested procedure.

关键词： FLEXIBLE MANUFACTURING HEURISTIC generalized assignment problem LOADING SYSTEM SETUP

来源：评论

学校读者我要写书评

暂无评论

THE SNOW DISPOSAL assignment problem

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 1995年第8期46卷 919-929页

作者： CAMPBELL, JF LANGEVIN, A GERAD MKONTREALPQCANADA ECOLE POLYTECH MONTREALPQ H3C 3A7CANADA

Snow removal and disposal are expensive winter activities that affect the quality of life and the environment in cities throughout the world. To facilitate traffic flow in urban regions that receive heavy snowfall, snow is first ploughed from streets and sidewalks and then hauled to disposal sites. A city is typically divided into many sectors that are cleared of snow concurrently. This paper briefly describes urban snow removal and disposal operations and analyses the snow disposal assignment problem for assigning snow removal sectors to snow disposal sites. The snow disposal assignment problem is formulated as a multi-resource generalized assignment problem. A two-phase heuristic solution procedure is developed, and solutions and sensitivity analyses are presented using data for the City of Montreal.

关键词： SNOW REMOVAL AND DISPOSAL URBAN LOGISTICS generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

MAXIMIZING A MONOTONE SUBMODULAR FUNCTION SUBJECT TO A MATROID CONSTRAINT

引用

SIAM JOURNAL ON COMPUTING 2011年第6期40卷 1740-1766页

作者： Calinescu, Gruia Chekuri, Chandra Pal, Martin Vondrak, Jan IIT Dept Comp Sci Chicago IL 60616 USA Univ Illinois Dept Comp Sci Urbana IL 61801 USA Google Inc New York NY 10018 USA IBM Almaden Res Ctr San Jose CA 95120 USA

Let f : 2(X) -> R+ be a monotone submodular set function, and let (X, I) be a matroid. We consider the problem max(S is an element of I)f(S). It is known that the greedy algorithm yields a 1/2-approximation [M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, Math. Programming Stud., no. 8 (1978), pp. 73-87] for this problem. For certain special cases, e. g., max(|S|<= k)f(S), the greedy algorithm yields a (1 - 1/e)-approximation. It is known that this is optimal both in the value oracle model (where the only access to f is through a black box returning f(S) for a given set S) [G. L. Nemhauser and L. A. Wolsey, Math. Oper. Res., 3 (1978), pp. 177-188] and for explicitly posed instances assuming P not equal NP [U. Feige, J. ACM, 45 (1998), pp. 634-652]. In this paper, we provide a randomized (1 - 1/e)-approximation for any monotone submodular function and an arbitrary matroid. The algorithm works in the value oracle model. Our main tools are a variant of the pipage rounding technique of Ageev and Sviridenko [J. Combin. Optim., 8 (2004), pp. 307-328], and a continuous greedy process that may be of independent interest. As a special case, our algorithm implies an optimal approximation for the submodular welfare problem in the value oracle model [J. Vondrak, Proceedings of the 38th ACM Symposium on Theory of Computing, 2008, pp. 67-74]. As a second application, we show that the generalized assignment problem (GAP) is also a special case;although the reduction requires |X| to be exponential in the original problem size, we are able to achieve a (1 - 1/e - o(1))-approximation for GAP, simplifying previously known algorithms. Additionally, the reduction enables us to obtain approximation algorithms for variants of GAP with more general constraints.

关键词： monotone submodular set function matroid social welfare generalized assignment problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

PRIMAL BEATS DUAL ON ONLINE PACKING LPs IN THE RANDOM-ORDER MODEL

引用

SIAM JOURNAL ON COMPUTING 2018年第5期47卷 1939-1964页

作者： Kesselheim, Thomas Radke, Klaus Toennis, Andreas Voecking, Berthold TU Dortmund Dortmund Germany Rhein Westfal TH Aachen Aachen Germany Univ Bonn Bonn Germany

We study packing linear programs (LPs) in an online model where the columns are presented to the algorithm in random order. This natural problem was investigated in various recent studies motivated, e.g., by online ad allocations and yield management, where rows correspond to resources and columns to requests specifying demands for resources. Our main contribution is a 1 - O(root(log d)/B)-competitive online algorithm. Here d denotes the column sparsity, i.e., the maximum number of resources that occur in a single column, and B denotes the capacity ratio B, i.e., the ratio between the capacity of a resource and the maximum demand for this resource. In other words, we achieve a (1 - is an element of)-approximation if the capacity ratio satisfies B = Omega(log d/is an element of(2)), which is known to be the best possible for any (randomized) online algorithms. Our result improves exponentially on previous work with respect to the capacity ratio. In contrast to existing results on packing LP problems, our algorithm does not use dual prices to guide the allocation of resources over time. Instead, the algorithm simply solves, for each request, a scaled version of the partially known primal program and randomly rounds the obtained fractional solution to obtain an integral allocation for this request. We show that this simple algorithmic technique is not restricted to packing LPs with large capacity ratio of order Q(log d), but also yields close-to-optimal competitive ratios if the capacity ratio is bounded by a constant. In particular, we prove an upper bound on the competitive ratio of Omega(d(-1)/(B-1)) for any B >= 2. In addition, we show that our approach can be combined with VCG payments and obtain an incentive-compatible (1 - is an element of)-competitive mechanism for packing LPs with B = Omega(log m/is an element of(2)), where m is the number of constraints. Finally, we apply our technique to the generalized assignment problem for which we obtain the first online

关键词： secretary problem packing linear program generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：