On nonlinear multi-covering problems

In this paper we define the exact k-coverage problem, and study it for the special cases of intervals and circular-arcs. Given a set system consisting of a ground set of n points with integer demands \(\{d_0,\dots ,d_{n-1}\}\) and integer rewards, subsets of points, and an integer k, select up to k subsets such that the sum of rewards of the covered points is maximized, where point i is covered if exactly \(d_i\) subsets containing it are selected. Here we study this problem and some related optimization problems. We prove that the exact k-coverage problem with unbounded demands is NP-hard even for intervals on the real line and unit rewards. Our NP-hardness proof uses instances where some of the natural parameters of the problem are unbounded (each of these parameters is linear in the number of points). We show that this property is essential, as if we restrict (at least) one of these parameters to be a constant, then the problem is polynomial time solvable. Our polynomial time algorithms are given for various generalizations of the problem (in the setting where one of the parameters is a constant).     

Trade shows and the creation of market and industry

This study addresses the question of the constitution of markets in advanced societies. Specifically, the article studies the role of the traveling trade show in creating the real time computing market, which is part of the US electronics sector, during the mid‐1990's. Real time computing products assist the transfer, storage and processing of digital signals in real time and support many of the internet applications we use today. By applying ethnographic methods, we explore the general question of how economic actors cope with uncertainty in the phase of market‐making and at the cutting edge of technology. The paper makes two contributions to the existing literature. First, it shows that the attempt to organize a trade show in real time computing was triggered by the uncertainty experienced by sellers regarding the identity of prospective buyers and about the exact use to which they would put the emergent technology which is offered for sale. Secondly, we trace the history of an emergent market. We claim that trade shows for innovative products are important venues at which markets coalesce. The identification and ordering of market actors, the institutionalization of a distinct business culture and the social networks developed among market actors and across the subsidiary markets provided the basic social infrastructure for what later became known as the real time computing industry.     

Min-Sum Bin Packing

We study min-sum bin packing (MSBP). This is a bin packing problem, where the cost of an item is the index of the bin into which it is packed. The problem is equivalent to a batch scheduling problem we define, where the total completion time is to be minimized. The problem is NP-hard in the strong sense. We show that it is not harder than this by designing a polynomial time approximation scheme for it. We also show that several natural algorithms which are based on well-known bin packing heuristics (such as First Fit Decreasing) fail to achieve an asymptotic finite approximation ratio, whereas Next Fit Increasing has an absolute approximation ratio of at most 2, and an asymptotic approximation ratio of at most 1.6188. We design a new heuristic that applies Next Fit Increasing on the relatively small items and adds the larger items using First Fit Decreasing, and show that its asymptotic approximation ratio is at most 1.5604.     

Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem

We consider stochastic variants of the NP-hard 0/1 knapsack problem in which item values are deterministic and item sizes are independent random variables with known, arbitrary distributions. Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. The goal is to compute a policy for insertion of the items, that maximizes the expected value of the set of items placed in the knapsack. These variants that we study differ only in the formula for computing the value of the final solution obtained by the policy. We consider both nonadaptive policies (that designate a priori a fixed subset or permutation of items to insert) and adaptive policies (that can make dynamic decisions based on the instantiated sizes of the items placed in the knapsack thus far). Our work characterizes the benefit of adaptivity. For this purpose we use a measure called the adaptivity gap: the supremum over instances of the ratio between the expected value obtained by an optimal adaptive policy and the expected value obtained by an optimal non-adaptive policy. We show that while for the variants considered in the literature this quantity is bounded by a constant there are other variants where it is unbounded.     

Gifting Practices and Interorganizational Relations: Constructing Obligation Networks in the Electronics Sector

Sociologists and economic anthropologists often implicitly associate capitalist societies with the commodity form and preindustrial societies with the gift form. In contrast, this ethnographic study of the sales of electronics components shows that gifting and commodity exchange actually are inextricably intertwined in contemporary markets. Commodity exchange depends on obligation networks created and sustained, in part, by gifting and countergifting. Each juncture of the sales process has an associated type of gifting. Gifts provide the social basis for a moral economy that governs the construction of sales networks.     

Status,National Culture and Customers’ Propensity to Complain

People’s ability to express their voice in different situation is an important facet of their quality of life. This study examines the relationship between social status, cultural characteristics and customers’ voice behavior in multiple cultures. We hypothesized that social status would be positively related to customers’ voice expression. The cultural dimensions of power distance and uncertainty avoidance were expected to affect that behavior and to moderate the status–voicing relationship. Analysis of data concerning 8,479 customers from 12 countries showed that, as expected, customers with high status tended to register more service failures and to complain more frequently than customers of lower social status. All three social status distinctions explored in this study (gender, education, and age) correlated negatively with formal complaint, but only age correlated negatively with informal complaint. In addition, the two cultural dimensions had the expected negative effect on intention to complain, and moderated the relationship between social status and intention to complain. Theoretical contributions and applied implications are discussed.     

Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees

We consider two related problems: the multiple-depot vehicle routing problem (MDVRP) and the Multiple traveling salesman problem (mTSP). In both of them, given is the complete graph on n vertices \(G = (V,E)\) with nonnegative edge lengths that form a metric on V. Also given is a positive integer k. In typical applications, V represents locations of customers and k represents the number of available vehicles. In MDVPR, we are also given a set of k depots \(\{O_1,\ldots ,O_k\} \subseteq V\) , and the goal is to find a minimum-length cycle cover of G of size k, that is, a collection of k (possibly empty) cycles such that each \(v \in V\) is in exactly one cycle, and each cycle in the cover contains exactly one depot. In mTSP, no depots are given, so the goal is to find (any) minimum-length cycle cover of G of size k. We present local search algorithms for both problems, and we prove that their approximation ratio is 2.     

Selfish bin coloring

The bin packing problem, a classical problem in combinatorial optimization, has recently been studied from the viewpoint of algorithmic game theory. In this bin packing game each item is controlled by a selfish player minimizing its personal cost, which in this context is defined as the relative contribution of the size of the item to the total load in the bin.     

Ethnic social capital: Individual and group level sources and their economic consequences

Ethnic social capital shapes economic action by immigrants by providing information, training, and credit that is otherwise unavailable. However, prior research on the effects of ethnic social capital on economic attainment by salaried workers primarily relied on case studies of specific destinations or ethnic groups. Furthermore, prior research focused on group level effects of ethnic social capital while largely ignoring the effects of individual-level utilization of ethnic ties. This study addresses these limitations by combining data from the New Immigrant Survey and the 5% file of the 2000 US Census. This allows controlling for group differences in actual utilization of familial ties and for differences between groups in their demographic makeup, legal status, and human capital when estimating the effect of ethnic social capital. It also allows addressing the potentially divergent implications of ethnic social capital for individual and group economic attainment. Results suggest that, on both the individual and group levels, reliance on ethnic social capital is associated with lower earnings for recent legal immigrants to the US.     

Coopting Change toward Industrial Democracy: Professionals as Agents of Structural Constraint

This paper asks why the democratic election of leaders, which is so fundamental an institution in much of Western society, is held sacred in the political sector of social life but rejected in the economic one. We propose that democracy stops at the factory gates partly because of the practices and ideologies of practice of the professionals who construct and maintain the boundaries between the workplace and the larger political sphere. Specifically, we compare the role of lawyers, accountants, and academics in situations where workers attempt to implement or maintain a democratic governance structure in the workplace, within a socialist and a capitalist economic order. We conclude that professionals act as cooptation agents for democratic ideas in both the capitalist and the socialist context.