8 results on '"Assignment problem"'
Search Results
2. Algorithms and Fundamental Limits for Unlabeled Detection Using Types.
- Author
-
Marano, Stefano and Willett, Peter K.
- Subjects
- *
GREEDY algorithms , *DETECTION limit , *SENSOR networks , *GENOMICS , *ALGORITHMS , *GENETIC techniques - Abstract
We deal with the classical problem of testing two simple statistical hypotheses but, as a new element, it is assumed that the data vector is observed after an unknown permutation of its entries. What is the fundamental limit for the detection performance in this case? How much information for detection is contained in the entry values and how much in their positions? In the first part of this paper, we answer these questions. In the second part, we focus on practical algorithms. A low-complexity detector solves the detection problem without attempting to estimate the permutation. A modified version of the auction algorithm is then considered, and two greedy algorithms with affordable worst case complexity are presented. The detection operational characteristics of these detectors are investigated by computer experiments. The problem we address is referred to as unlabeled detection and is motivated by large sensor network applications, but applications are also foreseen in different fields, including image processing, social sensing, genome research, and molecular communication. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
3. Methodology for Multipath-Component Tracking in Millimeter-Wave Channel Modeling.
- Author
-
Lai, Chiehping, Sun, Ruoyu, Gentile, Camillo, Papazian, Peter B., Wang, Jian, and Senic, Jelena
- Subjects
- *
MULTIPATH channels , *ANTENNAS (Electronics) , *MIMO systems , *BANDWIDTHS , *SIGNAL processing - Abstract
We describe an extensive channel-measurement campaign, including 325 unique transmitter–receiver configurations, conducted in a lecture room with our 3-D double-directional 60 GHz channel sounder. The receiver was mounted on a mobile robot, with 40 cm spacing between channel acquisitions, enabling the tracking of clustered multipath components in the multidimensional delay-angle space. To mitigate against angle-estimation error and multipath blockage, we introduce a robust tracking algorithm based on the Assignment Problem. For the purpose of validation, the clusters were transformed from the delay-angle space onto a 2-D map of the environment and compared against the locations of cluster-generating reflectors, such as walls and tables. The location errors were typically within 30–50 cm. The clusters identified were then reduced to a stochastic map-based channel model, including reflection loss and dispersion characteristics such as the Ricean K-factor and angular spread. Given the 0.5 ns delay resolution of the channel sounder and angle-estimation error around 2°, the parameters were reported with high fidelity. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
4. A Mathematical Programming Solution for Automatic Generation of Synthetic Power Flow Cases.
- Author
-
Schweitzer, Eran and Scaglione, Anna
- Subjects
- *
ELECTRIC power production , *MATHEMATICAL programming , *ELECTRIC power systems , *ENERGY shortages , *ELECTRIC impedance - Abstract
A shortage of large power system data sets, as well as the frequent restrictions on sharing such models, have led to newfound interest in creating synthetic data that can be easily shared among researchers. This paper considers the problem of forming a power system test case from the constituent parts of realistic power grid samples. Starting from a topology, and samples of generation, load, and branches, we assemble systems while respecting the constraints imposed by a typical Optimal Power Flow problem. Expressed in this manner, the problem involves solving for permutations of the input data. Since permutations matrices are binary, the problem is linearized, allowing for a Mixed Integer Linear Problem formulation. The problem is further decomposed using the Alternating Direction Method of Multipliers as well as an Evolutionary Algorithm to facilitate scaling to larger system sizes. A post processing step is used to add shunt elements for reactive power planning. The resulting systems demonstrate statistically similar power flow behavior to reference systems. Finally, new analysis avenues, opened by synthesizing test cases according to the proposed method, are briefly introduced by creating fictitious systems with different topology models and examining how these affect power flow behavior. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
5. Application of Graph Theory to the Multicell Beam Scheduling Problem.
- Author
-
Dartmann, Guido, Gong, Xitao, and Ascheid, Gerd
- Subjects
- *
COMPUTERS in graph theory , *COMBINATORIAL optimization , *MATHEMATICAL optimization , *BEAMFORMING , *MATHEMATICAL models , *SIGNAL-to-noise ratio - Abstract
This paper applies combinatorial optimization techniques to improve the downlink transmission to multiple users in a network with N cells, where intercell interference is a performance-limiting factor. A fair distribution of the signal-to-interference-plus-noise ratio (SINR) is desirable. A well-known technique to get a fair (balanced) SINR is max–min unicast beamforming (MBF). However, in a multicell network, there are conditions where MBF can result in a low balanced SINR. This happens if, e.g., two users are geographically close together and served by two base stations (BSs) from, e.g., two different interfering sectors. Then, the mutual interference among the two links will be large, and the balanced SINR among all jointly optimized links decreases. Therefore, the users must be scheduled such that these situations are avoided. In this paper, smart selection of active beams to avoid intercell interference is called beam scheduling and leads to a combinatorial optimization problem. This paper proposes a graph-theory-based problem that is closely related to the beam scheduling problem. The proposed algorithms maximize the sum rate or the minimum SINR among all users and slots. For the two-cell case, an optimal algorithm exists. In the N > \2-cell case, the beam scheduling problem is proven to be NP-hard. Based on the close relation between the beam scheduling problem and the multidimensional assignment problem (MAP), this paper presents suboptimal algorithms for N > \2 to maximize either the sum rate or the minimum SINR among all users and slots. The performance gain in terms of the mean sum rate or the minimum SINR is significant compared with random scheduling. [ABSTRACT FROM PUBLISHER]
- Published
- 2013
- Full Text
- View/download PDF
6. Group Role Assignment via a Kuhn–Munkres Algorithm-Based Solution.
- Author
-
Zhu, Haibin, Zhou, MengChu, and Alkins, Rob
- Subjects
- *
CYBERNETICS , *SENSOR networks , *ALGORITHMS , *ORGANIZATIONAL structure , *DATA mining - Abstract
Role assignment is a critical task in role-based collaboration. It has three steps, i.e., agent evaluation, group role assignment, and role transfer, where group role assignment is a time-consuming process. This paper clarifies the group role assignment problem (GRAP), describes a general assignment problem (GAP), converts a GRAP to a GAP, proposes an efficient algorithm based on the Kuhn–Munkres (K-M) algorithm, conducts numerical experiments, and analyzes the solutions' performances. The results show that the proposed algorithm significantly improves the algorithm based on exhaustive search. The major contributions of this paper include formally defining the GRAPs, giving a general efficient solution for them, and expanding the application scope of the K-M algorithm. This paper offers an efficient enough solution based on the K-M algorithm that outperforms significantly the exhaustive search approach. [ABSTRACT FROM PUBLISHER]
- Published
- 2012
- Full Text
- View/download PDF
7. Assignment and Scheduling in Flexible Job-Shops by Hierarchical Optimization.
- Author
-
Zribi, Nozha, Kacem, Imed, El Kamel, Abdelkader, and Borne, Pierre
- Subjects
- *
SCHEDULING , *JOB shops , *ALGORITHMS , *ASSIGNMENT problems (Programming) , *HEURISTIC - Abstract
The article presents a study which proposes a new hierarchical method for the flexible job-shop scheduling problem (FJSP). The FJSP is a nondeterministic polynomial-time hard since it is an extension of the job-shop scheduling problem. The first method proposed is based successively on a heuristic approach and a local search. The second one is based on a branch-and-bound algorithm.
- Published
- 2007
- Full Text
- View/download PDF
8. Robust Contour Matching Via the Order-Preserving Assignment Problem.
- Author
-
Scott, Clayton and Nowak, Robert
- Subjects
- *
ROBUST control , *DYNAMIC programming , *MPEG (Video coding standard) , *MACHINE theory , *MACHINE translating , *DETECTORS - Abstract
A common approach to determining corresponding points on two shapes is to compute the cost of each possible pairing of points and solve the assignment problem (weighted bipartite matching) for the resulting cost matrix. We consider the problem of solving for point correspondences when the shapes of interest are each defined by a single, closed contour. A modification of the standard assignment problem is proposed whereby the correspondences are required to preserve the ordering of the points induced from the shapes' contours. Enforcement of this constraint leads to significantly improved correspondences. Robustness with respect to outliers and shape irregularity is obtained by required only a fraction of feature points to be matched. Furthermore, the minimum matching size may be specified in advance. We present efficient dynamic programming algorithms to solve the proposed optimization problem. Experiments on the Brown and MPEG-7 shape databases demonstrate the effectiveness of the proposed method relative to the standard assignment problem. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.