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

Design of logical topologies: A linear formulation or wavelength-routed optical networks with no wavelength changers

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2001年第2期9卷 186-198页

作者： Krishnaswamy, RM Sivarajan, KN Indian Inst Sci Dept Elect Commun Engn Bangalore 560012 Karnataka India

We consider the problem of constructing logical topologies over a wavelength-routed optical network with no wavelength changers. We present a general linear formulation which considers routing traffic demands, and routing and assigning wavelengths to lightpaths, as a combined optimization problem. The formulation also takes into account the maximum number of hops a lightpath is permitted to take, multiple logical links in the logical topology, multiple physical links in the physical topology, and symmetry/asymmetry restrictions in designing logical topologies. The objective is to minimize congestion, We show by examples how equality and inequality logical degree constraints have a bearing on congestion. We prove that, under certain renditions, having equality degree constraints with multiple edges allowed in the design of logical topologies does not affect congestion. This helps in reducing the dimensionality of the search space and hence speeds up the search for an optimal solution of the linear formulation. We solve the linear formulation for small examples and show the tradeoff between congestion, number of wavelengths available and the maximum number of hops a lightpath is allowed to take. For large networks, we solve the linear formulation by relaxing the integer constraints. We develop topology design algorithms for large networks based on rounding the solutions obtained by solving the relaxed problem, Since the whole problem is linearizable, the solution obtained by relaxation of the integer constraints yields a lower bound on congestion. This is useful in comparing the efficiency of our heuristic algorithms. Following Bienstock and Gunluk, 1995, we introduce a cutting plane which helps in obtaining better lower bounds on congestion and also enables us to reduce the previously obtained upper bounds on congestion.

关键词： all-optical networks linear program network planning topology design

来源：评论

学校读者我要写书评

暂无评论

Maximum packing channel assignment in cellular networks

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 1999年第3期48卷 858-872页

作者： Kulshreshtha, A Sivarajan, KN Indian Inst Technol IBM Solut Res Ctr Delhi 110016 India Indian Inst Sci Dept Elect Commun Engn Bangalore 560012 Karnataka India

We study the performance of the maximum packing channel assignment algorithm (MPA) in channelized cellular networks. MPA is a greedy algorithm, which rejects a call only when it is forced to do so, even if this involves rearrangement of channels assigned to the ongoing calls, without dropping any of them. We ignore handoffs and model the channel reuse constraints in the cellular network by a hypergraph [1], As the traffic and the number of channels are scaled together, we get a limiting regime where the blocking probability in the cells can be computed by solving a nonlinear optimization problem, The carried traffic in this limiting case is an upper bound on the performance of MPA for practical finite-channel systems. We show that the performance of MPA in a finite-channel cellular system can be closely approximated by considering a simple fixed-routing circuit-switched network. Thus, the finite-channel performance of MPA. can he studied using methods well known in the area of circuit-switched networks, We compare the performance of MPA with other asymptotically optimal algorithms and demonstrate its optimality for low and moderate offered traffic. We envisage MPA as a practical channel assignment algorithm, for moderate size systems, and suggest approximations to reduce its complexity.

关键词： channel assignment algorithm channel reassignment hypergraph linear program maximal independent set maximum packing algorithm optimization problem

来源：评论

学校读者我要写书评

暂无评论

Surface fitting and registration of point clouds using approximations of the unsigned distance function

引用

COMPUTER AIDED GEOMETRIC DESIGN 2010年第1期27卷 60-77页

作者： Floery, Simon Hofer, Michael Vienna Univ Technol Geometr Modeling & Ind Geometry Res Grp A-1040 Vienna Austria

Many problems in computer aided geometric design and geometry processing are stated as least-squares optimizations. Least-squares problems are well studied and widely used but exhibit immanent drawbacks such as high sensitivity to outliers. For this reason, we consider techniques for the registration of point clouds and surface fitting to point sets based on the l(1)-norm. We develop algorithms to solve l(1)-registration and l(1)-fitting problems and explore the emerging non-smooth minimization problems. We describe efficient ways to solve the optimization programs and present results for various applications. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Curve fitting Surface fitting Registration l(1)-approximation Optimization Proximal bundle method linear program Second-order cone programming

来源：评论

学校读者我要写书评

暂无评论

Determining Basic Variables of Optimal Solutions in Karmarkar's New LP Algorithm

引用

ALGORITHMICA 1986年第1-4期1卷 499-515页

作者： Kojima, Masakazu Tokyo Inst Technol Dept Informat Sci Meguro Ku Tokyo 152 Japan

This paper establishes a sufficient condition for a variable of a linear program to be positive at all optimal solutions. A numerical test using the condition is incorporated into Karmarkar's new LP algorithm to d... 详细信息

关键词： linear program Karmarkar's algorithm Optimal basis

来源：评论

学校读者我要写书评

暂无评论

Replica Placement and Access Policies in Tree Networks

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2008年第12期19卷 1614-1627页

作者： Benoit, Anne Rehn-Sonigo, Veronika Robert, Yves Univ Lyon Ecole Normale Super Lyon Lab Informat Parallellsme ENS Lyon CNRS INRIA UCBLUMR 5668 F-69364 Lyon France

In this paper, we discuss and compare several policies to place replicas in tree networks, subject to server capacity and Quality-of-Service (QoS) constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. The standard approach in the literature is to enforce that all requests of a client be served by the closest server in the tree. We introduce and study two new policies. In the first policy, all requests from a given client are still processed by the same server, but this server can be located anywhere in the path from the client to the root. In the second policy, the requests of a given client can be processed by multiple servers. One major contribution of this paper is to assess the impact of these new policies on the total replication cost. Another important goal is to assess the impact of server heterogeneity, both from a theoretical and a practical perspective. In this paper, we establish several new complexity results and provide several efficient polynomial heuristics for NP-complete instances of the problem. These heuristics are compared one to the other, and their absolute performance is assessed by comparison with the optimal solution provided by an integer linear program.

关键词： Replica placement tree networks access policy scheduling complexity results heuristics linear program heterogeneous clusters

来源：评论

学校读者我要写书评

暂无评论

A Novel Social Event Organization Approach for Diverse User Choices

引用

COMPUTER JOURNAL 2017年第7期60卷 1078-1095页

作者： Huang, Jianbin Zhou, Yu Jia, Xiaolin Sun, Heli Xidian Univ Sch Software Xian Shaanxi Peoples R China Xidian Univ Sch Comp Sci & Technol Sch Software Xian Shaanxi Peoples R China Xi An Jiao Tong Univ Dept Comp Sci & Technol Xian Shaanxi Peoples R China

The boom of social networking services makes it convenient to organize or participate in social events. Recent studies consider the social event organization problem, but they cannot provide diverse choices for users when there are multiple events. In this paper, we seek to devise an event organization scheme that provides diverse choices for users. For this goal, we explicitly distinguish the subjective preferences of users to events and the objective preferences of users to events. The former is considered to be the generative probabilities of users appearing in events, and the latter is viewed as the posterior probabilities of users participating in events. The Expectation-Maximization algorithm is employed to connect them together. After extracting these features, we extract an edge-weighted bipartite graph as the scheme from all the objective preferences. It captures the maximum sum of the objective preferences, and simultaneously satisfies soft user capacity constraints and hard event capacity constraints. We prove this problem is in P via transforming it into linear program (LP). In consideration that LP may have no feasible solutions, we alternatively devise an efficient polynomial time algorithm which can yield an approximately feasible solution. Experimental evaluation shows the effectiveness and efficiency of our proposed method.

关键词： social event organization ranking EM algorithm linear program

来源：评论

学校读者我要写书评

暂无评论

BREAKING 1-1/e BARRIER FOR NONPREEMPTIVE THROUGHPUT MAXIMIZATION

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2020年第3期34卷 1649-1669页

作者： Im, Sungjin Li, Shi Moseley, Benjamin Univ Calif Elect Engn & Comp Sci Merced CA 95343 USA Univ Buffalo Buffalo NY 14221 USA Carnegie Mellon Univ Pittsburgh PA 15213 USA

In this paper we consider one of the most basic scheduling problems where jobs have their respective arrival times and deadlines. The goal is to schedule as many jobs as possible nonpreemptively by their respective deadlines on m identical parallel machines. For the last decade, the best approximation ratio known for the single-machine case (m = 1) has been 1 - 1/e - epsilon approximate to 0.632 due to Chuzhoy, Ostrovsky, and Rabani [FOCS 2001] and NOR 2006]. We break this barrier and give an improved 0.644-approximation. For the multiple-machine case, we give an algorithm whose approximation guarantee becomes arbitrarily close to 1 as the number of machines increases. This improves upon the previous best 1 - 1/(1+1/m)(m) approximation due to Bar-Noy et al. [STOC 1999] and [SICOMP 2009], which converges to 1 - 1/e as m goes to infinity. Our result for the multiple-machine case extends to the weighted throughput objective where jobs have different weights, and the goal is to schedule jobs with the maximum total weight. Our results show that the 1 - 1/e approximation factor widely observed in various coverage problems is not tight for the nonpreemptive maximum throughput scheduling problem.

关键词： scheduling approximation nonpreemptive throughput linear program rounding

来源：评论

学校读者我要写书评

暂无评论

A Consistency and Consensus-Based Goal programming Method for Group Decision-Making With Interval-Valued Intuitionistic Multiplicative Preference Relations

引用

IEEE TRANSACTIONS ON CYBERNETICS 2019年第10期49卷 3640-3654页

作者： Zhang, Zhiming Pedrycz, Witold Hebei Univ Coll Math & Informat Sci Baoding 071002 Peoples R China Univ Alberta Dept Elect & Comp Engn Edmonton AB T6R 2V4 Canada King Abdulaziz Univ Dept Elect & Comp Engn Fac Engn Jeddah 21589 Saudi Arabia Polish Acad Sci Syst Res Inst PL-01447 Warsaw Poland

Interval-valued intuitionistic multiplicative preference relations (IVIMPRs) form a suitable conceptual framework to represent and process simultaneously uncertain preferred and nonpreferred judgments of decision makers (DMs). The thous of this paper is On group decision-making (GDM) problems realized with IVIMPRs. First, a consistency index is introduced to evaluate the consistency degree for intuitionistic multiplicative preference relations (IMPRs), and a consistency optimization approach is presented to jointly improve the consistency degrees of several IMPRs that do not satisfy the predefined consistency threshold. Then, a consistency definition and an acceptable consistency definition for IVIMPRs are established by splitting an IVIMPR into two IMPRs. For several IVIMPRs with unacceptable consistency, a goal program-based approach is proposed to simultaneously improve their consistency. Subsequently, by minimizing the degree to which the opinions of individual DMs deviate from those of the group, a maximum consensus-based goal program is established to determine the DMs' weights. Furthermore, an aggregation approach is applied to integrate individual IVIMPRs into a collective one. A linear program is then built to determine the interval-valued intuitionistic multiplicative priority weights of alternatives coming from the collective IVIMPR. A consistency-based GDM algorithm is proposed. Finally, a practical example is offered to show the application of the new algorithm, and a comparative analysis is presented to highlight the advantages of the new method.

关键词： Consistency group decision-making (GDM) interval-valued intuitionistic multiplicative preference relation (IVIMPR) intuitionistic multiplicative preference relation (IMPR) linear program

来源：评论

学校读者我要写书评

暂无评论

On retiming for FPGA logic module minimization

引用

INTEGRATION-THE VLSI JOURNAL 1997年第2期24卷 135-145页

作者： Chen, YP Wong, DF Univ Texas Dept Comp Sci Austin TX 78712 USA

In this paper, we consider the problem of minimizing the number of logic modules for Actel 2 or Actel 3 sequential circuits. We make use of the fact that if a flip-flop is the only destination of its driving combinational block, then both the flip-flop and the combinational block can be put in a sequential module. Retiming technique is applied to minimize the number of registers that cannot be merged with combinational blocks. We formulate the problem as an integer linear program. We show that the constraint matrix of the integer program is totally unimodular. As a result, we can solve our logic module minimization problem optimally by solving the linear relaxation of the integer program.

关键词： FPGA logic module retiming linear program

来源：评论

学校读者我要写书评

暂无评论

Size Constrained Clustering With MILP Formulation

引用

IEEE ACCESS 2020年 8卷 1587-1599页

作者： Tang, Wei Yang, Yang Zeng, Lanling Zhan, Yongzhao Jiangsu Univ Sch Comp Sci & Commun Engn Zhenjiang 212013 Jiangsu Peoples R China

Clustering is one of the essential tools for data mining since it reveals the natural structures of the unlabeled data. Many clustering algorithms have been proposed in the last decades. However, few of them are designed to adapt prior knowledge that is available in many real applications, such as the sizes of clusters. In this paper, we propose a novel iterative clustering algorithm that can impose the constraints on the sizes of clusters. Given an unordered set of cluster size constraints, the proposed method minimizes the mean squared error (MSE) while simultaneously considers the size constraints. Each iteration of the proposed method consists of two steps, namely an assignment step and an update step. In the assignment step, the observations are assigned into clusters under the size constraints. The assignment task is modeled as an integer linear programming (ILP) problem. We prove that part of the constraint matrix of this ILP problem is total unimodular. Therefore, the integer constraints on most of the variables can be omitted so that the problem would become a mixed integer programming (MILP) problem which is much easier to solve. In the update step, new cluster centroids will be updated as the centers of the observations in the corresponding clusters. Experiments on UCI data sets indicate that (1) imposing the size constraints as proposed could improve the clustering performance;(2) compared with the state-of-the-art size constrained clustering methods, the proposed method could efficiently derive better clustering results.

关键词： Clustering mean squared error size constraints linear program

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：