Search

We show that a very general hypersurface of degree d at least 4 and dimension at most $(d+1)2^{d-4}$ over a field of characteristic different from 2 does not admit a decomposition of the diagonal; hence, it is neither stably nor retract rational, nor $\mathbb{A}^1$-connected. Similar results hold in characteristic 2 under a slightly weaker degree bound. This improves earlier results by the second named author and Moe., Comment: 37 pages

We generalize a recent result of Pavic--Schreieder regarding the surjectivity of the obstruction morphism defined in [PS23]. As a consequence of this result, we show that geometrically (retract) rational varieties over a Laurent field of characteristic 0, which admit a strictly semi-stable model, have trivial Chow group of zero-cycles. Our key new ingredient comes from toric geometry., Comment: 28 pages

The energy transition in transportation benefits from demand-based models to determine the optimal placement of refueling stations for alternative fuel vehicles such as battery electric trucks. A formulation known as the refueling station location problem with routing (RSLP-R) is concerned with minimizing the number of stations necessary to cover a set of origin-destination trips such that the transit time does not exceed a given threshold. In this paper we extend the RSLP-R by station capacities to limit the number of vehicles that can be refueled at individual stations. The solution to the capacitated RSLP-R (CRSLP-R) avoids congestion of refueling stations by satisfying capacity constraints. We devise two optimization methods to deal with the increased difficulty to solve the CRSLP-R. The first method extends a prior branch-and-cut approach and the second method is a branch-cut-and-price algorithm based on variables associated with feasible routes. We evaluate both our methods on instances from the literature as well as a newly constructed network and find that the relative performance of the algorithms depends on the strictness of the capacity constraints. Furthermore, we show some runtime improvements over prior work on uncapacitated instances.

We show that a very general (3,3) complete intersection in $\mathbb{P}^7$ over an algebraically closed uncountable field of characteristic different from 2 admits no decomposition of the diagonal, in particular it is not retract rational. This strengthens Nicaise--Ottem's result, where stable irrationality in characteristic 0 was shown. The main tool is a Chow-theoretic obstruction which was found by Pavic--Schreieder, where quartic fivefolds are studied., Comment: 20 pages, final version, to appear in Annales de l'Institut Fourier

Fundamental to many applications in data analysis are the decompositions of a graph, i.e. partitions of the node set into component-inducing subsets. One way of encoding decompositions is by multicuts, the subsets of those edges that straddle distinct components. Recently, a lifting of multicuts from a graph $G = (V, E)$ to an augmented graph $\hat G = (V, E \cup F)$ has been proposed in the field of image analysis, with the goal of obtaining a more expressive characterization of graph decompositions in which it is made explicit also for pairs $F \subseteq \tbinom{V}{2} \setminus E$ of non-neighboring nodes whether these are in the same or distinct components. In this work, we study in detail the polytope in $\mathbb{R}^{E \cup F}$ whose vertices are precisely the characteristic vectors of multicuts of $\hat G$ lifted from $G$, connecting it, in particular, to the rich body of prior work on the clique partitioning and multilinear polytope., Comment: 63 pages, 18 figures

We present a message passing method for 0-1 integer linear programs. Our algorithm is based on a decomposition of the original problem into subproblems that are represented as binary decision diagrams. The resulting Lagrangean dual is solved iteratively by a series of efficient block coordinate ascent steps. Our method has linear iteration complexity in the size of the decomposition and can be effectively parallelized. The characteristics of our approach are desirable towards solving ever larger problems arising in structured prediction. We present experimental results on combinatorial problems from MAP inference for Markov Random Fields, quadratic assignment, discrete tomography and cell tracking for developmental biology and show promising performance.

The NP-hard problem of correlation clustering is to partition a signed graph such that the number of conflicts between the partition and the signature of the graph is minimized. This paper studies graph signatures that allow the optimal partition to be found efficiently. We define the class of flow-partitionable signed graphs, which have the property that the standard linear programming relaxation based on so-called cycle inequalities is tight. In other words, flow-partitionable signed graphs satisfy an exact max-multiflow-min-multicut relation in the associated instances of minimum multicut. In this work we propose to characterize flow-partitionable signed graphs in terms of forbidden minors. Our initial results include two infinite classes of forbidden minors, which are sufficient if the positive subgraph is a circuit or a tree. For the general case we present another forbidden minor and point out a connection to open problems in the theory of ideal clutters.

In combinatorial optimization, partial variable assignments are called persistent if they agree with some optimal solution. We propose persistency criteria for the multicut and max-cut problem as well as fast combinatorial routines to verify them. The criteria that we derive are based on mappings that improve feasible multicuts, respectively cuts. Our elementary criteria can be checked enumeratively. The more advanced ones rely on fast algorithms for upper and lower bounds for the respective cut problems and max-flow techniques for auxiliary min-cut problems. Our methods can be used as a preprocessing technique for reducing problem sizes or for computing partial optimality guarantees for solutions output by heuristic solvers. We show the efficacy of our methods on instances of both problems from computer vision, biomedical image analysis and statistical physics.

Digital health interventions have been emerging in the last decade. Due to their interdisciplinary nature, digital health interventions are guided and influenced by theories (e.g., behavioral theories, behavior change technologies, persuasive technology) from different research communities. However, digital health interventions are always coded using various taxonomies and reported in insufficient perspectives. The inconsistency and incomprehensiveness will bring difficulty for conducting systematic reviews and sharing contributions among communities. Based on existing related work, therefore, we propose a holistic framework that embeds behavioral theories, behavior change technique (BCT) taxonomy, and persuasive system design (PSD) principles. Including four development steps, two toolboxes, and one workflow, our framework aims to guide digital health intervention developers to design, evaluate, and report their work in a formative and comprehensive way.

Increasing evidence has shown that theory-based health behavior change interventions are more effective than non-theory-based ones. However, only a few segments of relevant studies were theory-based, especially the studies conducted by non-psychology researchers. On the other hand, many mobile health interventions, even those based on the behavioral theories, may still fail in the absence of a user-centered design process. The gap between behavioral theories and user-centered design increases the difficulty of designing and implementing mobile health interventions. To bridge this gap, we propose a holistic approach to designing theory-based mobile health interventions built on the existing theories and frameworks of three categories: (1) behavioral theories (e.g., the Social Cognitive Theory, the Theory of Planned Behavior, and the Health Action Process Approach), (2) the technological models and frameworks (e.g., the Behavior Change Techniques, the Persuasive System Design and Behavior Change Support System, and the Just-in-Time Adaptive Interventions), and (3) the user-centered systematic approaches (e.g., the CeHRes Roadmap, the Wendel's Approach, and the IDEAS Model). This holistic approach provides researchers a lens to see the whole picture for developing mobile health interventions.

Prolonged sedentary behavior is prevalent among office workers and has been found to be detrimental to health. Preventing and reducing prolonged sedentary behavior require interventions, and persuasive technology is expected to make a contribution in this domain. In this paper, we use the framework of persuasive system design (PSD) principles to investigate the utilization and effectiveness of persuasive technology in intervention studies at reducing sedentary behavior at work. This systematic review reveals that reminders are the most frequently used PSD principle. The analysis on reminders shows that hourly PC reminders alone have no significant effect on reducing sedentary behavior at work, while coupling with education or other informative session seems to be promising. Details of deployed persuasive technology with behavioral theories and user experience evaluation are expected to be reported explicitly in the future intervention studies.

We study the problem of decomposing (clustering) a tree with respect to costs attributed to pairs of nodes, so as to minimize the sum of costs for those pairs of nodes that are in the same component (cluster). For the general case and for the special case of the tree being a star, we show that the problem is NP-hard. For the special case of the tree being a path, this problem is known to be polynomial time solvable. We characterize several classes of facets of the combinatorial polytope associated with a formulation of this clustering problem in terms of lifted multicuts. In particular, our results yield a complete totally dual integral (TDI) description of the lifted multicut polytope for paths, which establishes a connection to the combinatorial properties of alternative formulations such as set partitioning., Comment: v2 is a complete revision

This paper introduces a novel algorithm for transductive inference in higher-order MRFs, where the unary energies are parameterized by a variable classifier. The considered task is posed as a joint optimization problem in the continuous classifier parameters and the discrete label variables. In contrast to prior approaches such as convex relaxations, we propose an advantageous decoupling of the objective function into discrete and continuous subproblems and a novel, efficient optimization method related to ADMM. This approach preserves integrality of the discrete label variables and guarantees global convergence to a critical point. We demonstrate the advantages of our approach in several experiments including video object segmentation on the DAVIS data set and interactive image segmentation.

Lineage tracing, the joint segmentation and tracking of living cells as they move and divide in a sequence of light microscopy images, is a challenging task. Jug et al. have proposed a mathematical abstraction of this task, the moral lineage tracing problem (MLTP), whose feasible solutions define both a segmentation of every image and a lineage forest of cells. Their branch-and-cut algorithm, however, is prone to many cuts and slow convergence for large instances. To address this problem, we make three contributions: (i) we devise the first efficient primal feasible local search algorithms for the MLTP, (ii) we improve the branch-and-cut algorithm by separating tighter cutting planes and by incorporating our primal algorithms, (iii) we show in experiments that our algorithms find accurate solutions on the problem instances of Jug et al. and scale to larger instances, leveraging moral lineage tracing to practical significance., Comment: Accepted at ICCV 2017

We investigate conditions for the unique recoverability of sparse integer-valued signals from a small number of linear measurements. Both the objective of minimizing the number of nonzero components, the so-called $\ell_0$-norm, as well as its popular substitute, the $\ell_1$-norm, are covered. Furthermore, integrality constraints and possible bounds on the variables are investigated. Our results show that the additional prior knowledge of signal integrality allows for recovering more signals than what can be guaranteed by the established recovery conditions from (continuous) compressed sensing. Moreover, even though the considered problems are \NP-hard in general (even with an $\ell_1$-objective), we investigate testing the $\ell_0$-recovery conditions via some numerical experiments. It turns out that the corresponding problems are quite hard to solve in practice using black-box software. However, medium-sized instances of $\ell_0$- and $\ell_1$-minimization with binary variables can be solved exactly within reasonable time.

We study the set of all decompositions (clusterings) of a graph through its characterization as a set of lifted multicuts. This leads us to practically relevant insights related to the definition of a class of decompositions by must-join and must-cut constraints and related to the comparison of clusterings by metrics. To find optimal decompositions defined by minimum cost lifted multicuts, we establish some properties of some facets of lifted multicut polytopes, define efficient separation procedures and apply these in a branch-and-cut algorithm., Comment: ICML 2017