Language is ambiguous; many terms and expressions can convey the same idea. This is especially true in creative practice, where ideas and design intents are highly subjective. We present a dataset-Ambiguous Descriptions of Art Images (ADARI)-of contemporary workpieces, which aims to provide a foundational resource for subjective image description and multimodal word disambiguation in the context of creative practice. The dataset contains a total of 240k images labeled with 260k descriptive sentences. It is additionally organized into sub-domains of architecture, art, design, fashion, furniture, product design and technology. In subjective image description, labels do not necessarily correspond to well-defined entities i.e. cars, quantitative attributes such as the color red, or actions like playing. For example, the ambiguous label dynamic is a qualitative attribute of an extensive amount of objects and thus, the data's variance is high. To understand this complexity, we analyze the ambiguity and relevance of text with respect to images using the state-of-the-art pre-trained BERT model for sentence classification. We provide a baseline for multi-label classification tasks and demonstrate the potential of multimodal approaches for understanding ambiguity in design intentions. We hope that ADARI dataset and baselines constitute a first step towards subjective label classification.

In this paper, we propose a new primal heuristic for the Linear Ordering Problem (LOP) that generates an integer feasible solution from the solution to the LP relaxation at each node of the branch-and-bound search tree. The heuristic first finds a partition of the set of vertices S into an ordered pair of subsets {S1,S2} such that the difference between the weights of all arcs from S1 to S2 and the weights of all arcs from S2 to S1 is maximized. It then assumes that all vertices in S1 precede all vertices in S2 thus decomposing the original problem instance into subproblems of smaller size i.e. on subsets S1 and S2. It recursively does so until the subproblems can be solved quickly using an MIP solver. The solution to the original problem instance is then constructed by concatenating the solutions to the subproblems. The heuristic is used to propose integer feasible solutions for the branch-and-bound algorithm. We also devise an alternate node selection strategy based on the heuristic solutions where we select the node with the best heuristic solution. We report the results of our experiments with the heuristic and the node selection strategy based on the heuristic.

We consider the problem of fair allocation of indivisible goods where we are given a set I of m indivisible resources (items) and a set P of n customers (players) competing for the resources. Each resource j in I has a same value vj > 0 for a subset of customers interested in j and it has no value for other customers. The goal is to find a feasible allocation of the resources to the interested customers such that in the Max-Min scenario (also known as Santa Claus problem) the minimum utility (sum of the resources) received by each of the customers is as high as possible and in the Min-Max case (also known as R||C_max problem), the maximum utility is as low as possible. In this paper we are interested in instances of the problem that admit a PTAS. These instances are not only of theoretical interest but also have practical applications. For the Max-Min allocation problem, we start with instances of the problem that can be viewed as a convex bipartite graph; there exists an ordering of the resources such that each customer is interested (has positive evaluation) in a set of consecutive resources and we demonstrate a PTAS. For the Min-Max allocation problem, we obtain a PTAS for instances in which there is an ordering of the customers (machines) and each resource (job) is adjacent to a consecutive set of customers (machines). Next we show that our method for the Max-Min scenario, can be extended to a broader class of bipartite graphs where the resources can be viewed as a tree and each customer is interested in a sub-tree of a bounded number of leaves of this tree (e.g. a sub-path).

In this paper, we consider the problem where a point robot in a 2D or 3D environment equipped with an omnidirectional range sensor of finite range D is asked to cover a set of surface patches, while minimizing the sum of view cost, proportional to the number of viewpoints planned, and the travel cost, proportional to the length of path traveled. We call it the Metric View Planning Problem with Traveling Cost and Visibility Range or Metric TVPP in short. We present a complexity result for the problem, i.e., we show that the Metric TVPP cannot be approximated within O(log m) ratio by any polynomial algorithm, where m is the number of surface patches to cover. We then analyze a variant of an existing decoupled two-level algorithm of first solving the view planning problem to get an approximate solution, and then solving, again using an approximation algorithm, the Metric traveling salesman problem to connect the planned viewpoints. We then present performance bounds for this two-level decoupled algorithm, i.e., we show that it has an approximation ratio of O(log m). Thus, it asymptotically achieves the best approximation ratio one can hope for.

The Multicast/Broadcast Service (MBS) feature of mobile WiMAX network is a promising technology for providing wireless multimedia, because it allows the delivery of multimedia content to large-scale user communities in a cost-efficient manner. In this paper, we consider WiMAX networks that transmit multiple video streams encoded in scalable manner to mobile receivers using the MBS feature. We focus on two research problems in such networks: 1) maximizing the video quality and 2) minimizing energy consumption for mobile receivers. We formulate and solve the substream selection problem to maximize the video quality, which arises when multiple scalable video streams are broadcast to mobile receivers with limited resources. We show that this problem is NP-Complete, and design a polynomial time approximation algorithm to solve it. We prove that the solutions computed by our algorithm are always within a small constant factor from the optimal solutions. In addition, we extend our algorithm to reduce the energy consumption of mobile receivers. This is done by transmitting the selected substreams in bursts, which allows mobile receivers to turn off their wireless interfaces to save energy. We show how our algorithm constructs burst transmission schedules that reduce energy consumption without sacrificing the video quality. Using extensive simulation and mathematical analysis, we show that the proposed algorithm: 1) is efficient in terms of execution time, 2) achieves high radio resource utilization, 3) maximizes the received video quality, and 4) minimizes the energy consumption for mobile receivers.

Broadcasting multiple scalable video streams over wireless broadband access networks in real time is a challenging problem, because of the limited channel capacity and variable bit rate of the videos. The difficulty is further increased in the presence of receiver buffer size limitations which may introduce buffer overflow possibilities. The Multicast/Broadcast Service feature of mobile WiMAX network is a promising technology for providing wireless video broadcast services. In this article, we describe a substream selection problem which arises when multiple scalable video streams are broadcast based on the Multicast/Broadcast Service feature to a number of buffer size constrained receivers. We first show that the problem is NP-Complete and design a polynomial time approximation algorithm based on convex optimization and dynamic programming techniques. We mathematically prove that the solution obtained through our algorithm is always within a constant factor of the optimal solution. Through simulation we show that under real time requirements our algorithm provides solutions which are within 1 dB of the optimal solutions.

In this paper, we introduce the problem of view planning with combined view and traveling cost, denoted by traveling VPP. It refers to planning a sequence of sensing actions with minimum total cost by a robot-sensor system to completely inspect the surfaces of objects in a known workspace. The cost to minimize is a combination of the view cost, proportional to the number of viewpoints planned, and the traveling cost for the robot to realize them. First, we formulate traveling VPP as an integer linear program (ILP). The focus of this paper is to design an approximation algorithm that guarantees worst-case performance (w.r.t. the optimal solution cost). We propose a linear program based rounding algorithm that achieves an approximation ratio of the order of view frequency, defined to be the maximum number of viewpoints that see a single surface patch of the object. Together with the result we showed (2006), the best approximation ratio for Traveling VPP is either the order of view frequency or a poly-log function of the input size, whichever is smaller. Motivated from the robot motion planning techniques, where the graph built for robot traveling is a tree, we then consider the corresponding special case of traveling VPP, and give a polynomial sized LP formulation. We conclude with a discussion of realistic issues and constraints towards implementing our algorithm on real robot-sensor systems.

In this paper, we consider the problem where a point robot in a 2D or 3D environment equipped with an omnidirectional range sensor of finite range D is asked to inspect a set of surface patches, while minimizing the sum of view cost, proportional to the number of viewpoints planned, and the travel cost, proportional to the length of path traveled. We call it the metric view planning problem with traveling cost and visibility range or metric TVPP in short. Via an L-reduction from the set covering problem to a two-dimensional metric TVPP, we show that the metric TVPP cannot be approximated within O(log m) ratio by any polynomial algorithm, where m is the number of surface patches to cover. We then analyze the natural two-level algorithm, presented by Danner and Kavraki (2002), of solving first the view planning problem to get an approximate solution, and then solving, again using an approximation algorithm, the Metric traveling salesman problem to connect the planned viewpoints. We show this greedy algorithm has the approximation ratio of O(log m). Thus, it asymptotically achieves the best approximation ratio one can hope for.

Vehicle routing problems involve the navigation of one or more vehicles through a network of locations. Locations have associated handling times as well as time windows during which they are active. The arcs connecting locations have time costs associated with them. In this paper, we consider two different problems in single vehicle routing. The first is to find least time cost routes between all pairs of nodes in a network for navigating vehicles; we call this the all pairs routing problem. We show that there is an O(log/sup 2/ n) time parallel algorithm using a polynomial number of processors for this problem on a CREW PRAM. We next consider the problem in which a vehicle services all locations in a network. Here, locations can be passed through at any time but only serviced during their time window. The general problem is NP-complete under even fairly stringent restrictions but polynomial algorithms have been developed for some special cases. In particular, when the network is a line, there is no time cost in servicing a location, and all time windows are unbounded at either their lower or upper end, O(n/sup 2/) algorithms have been developed. We show that under the same conditions, we can reduce this problem to the all pairs routing problem and therefore obtain an O(log/sup 2/ n) time parallel algorithm on a CREW PRAM.

This paper analyzes the worst-case performance of combinations of greedy heuristics for the integer knapsack problem. If the knapsack is large enough to accomodate at least m units of any item, then the joint performance of the total-value and density-ordered greedy heuristics is no smaller than (m + 1)(m + 2). For combinations of greedy heuristics that do not involve both the density-ordered and total-value greedy heuristics, the worst-case performance of the combination is no better than the worst-case performance of the single best heuristic in the combination.

This paper addresses the problem of preemptive scheduling on parallel-task systems. A parallel-task system consists of several independent tasks, each of which can be executed on one or more processors. Du and Leung introduced the problem of minimizing the schedule length in parallel-task systems and showed that it is strongly NP-hard for both nonpreemptive and preemptive scheduling of independent tasks. This paper presents a polynomial-time approximation algorithm for preemptive scheduling of a parallel-task system with n processors and w tasks. We derive a tight worst-case performance bound of r for the approximation algorithm, where r is the maximum factor by which we can increase the number of processors on which a task can be executed. For example, $r = 2$ in the model defined by Du and Leung for parallel-task systems in which a task can be executed on any integral number of processors.

This paper shows that a minimization version of satisfiability is strongly NP-hard, even if each clause contains no more than two literals and/or each clause contains at most one unnegated variable. The worst-case and average-case performances of greedy and probabilistic greedy heuristics for the problem are examined, and tight upper bounds on the performance ratio in each case are developed.

A partitionable multiprocessor system can form multiple partitions, each consisting of a controller and a varying number of processors. Given such a system and a set of tasks, each of which can be executed on partitions of varying sizes, the authors study the problem of choosing the partition sizes and a minimum completion time schedule for the execution of these tasks. They assume that the number of tasks to be scheduled on the system is no more than the maximum number of partitions that can be formed simultaneously by the system, and that parallelization of the tasks can achieve at most perfect speedup. They show this scheduling problem to be NP-hard, and present a polynomial time approximation algorithm for this problem. The authors derive a parameter dependent, asymptotically tight worst-case performance bound for the algorithm, and evaluate its average performance through simulation.>

Distribution-free tight lower bounds on the average performance ratio for random search, for a greedy heuristic and for a probabilistic greedy heuristic are derived for an optimization version of satisfiability. On average, the random solution is never worse than $\frac{1}{2}$ of the optimal, regardless of the data-generating distribution. The lower bound on the average greedy solution is at least $\frac{1}{2}$ of the optimal, and this bound increases with the probability of the greedy heuristic selecting the optimal at each step. In the probabilistic greedy heuristic, probabilities are introduced into the search strategy so that a decrease in the probability of finding the optimal solution occurs only if the nonoptimal solution becomes closer to the optimal. Across problem instances, and regardless of the distribution giving rise to data, the minimum average value of the solutions identified by the robabilistic greedy heuristic is no less than $\frac{2}{3}$ of the optimal.

This paper discusses the semantics of the GKS inquiry functions within a Prolog environment and illustrates the flexibility built into a proposed Prolog binding.